1
$\begingroup$

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$?

$\endgroup$

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .