Let $G$ be a $2$-connected graph and for $e \in E(G)$ denote by $\mathcal{C_e}$ the set of all cycles of $G$ containing the edge $e$.
For what set of edges does $\mathcal{C_e}$ contain a basis of the cycle space of $G$?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityLet $G$ be a $2$-connected graph and for $e \in E(G)$ denote by $\mathcal{C_e}$ the set of all cycles of $G$ containing the edge $e$.
For what set of edges does $\mathcal{C_e}$ contain a basis of the cycle space of $G$?
For all $e \in E(G)$, $\mathcal{C}_e$ contains a basis of the cycle space.
Proof. Let $e=uv \in E(G)$, and let $C$ be a cycle of $G$. If $e \in E(C)$, then there is nothing to show. Thus, $e \notin E(C)$. By Menger's theorem, there are two disjoint paths $P_u$ and $P_v$ from $\{u,v\}$ to $V(C)$. By taking $P_u$ and $P_v$ to so that $|P_u|+|P_v|$ is minimal, we may assume that $P_u$ and $P_v$ each meet $C$ once. Thus, $e \cup E(P_u) \cup E(P_v) \cup E(C)$ is a $\theta$-subgraph, and it is easy to see that $C$ is the symmetric difference of two cycles $C_1$ and $C_2$, both of which contain $e$.