Let $G$ be a $2$-connected graph and for $e \in E(G)$ denote by $\mathcal{C_e}$ the set of all cycles(circuits) of $G$ containing the edge $e$.

For what set of edges does $\mathcal{C_e}$ contain a basis of the Cycle Subspace 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 community
Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

0

$\begingroup$
$\endgroup$

Let $G$ be a $2$-connected graph and for $e \in E(G)$ denote by $\mathcal{C_e}$ the set of all cycles(circuits) of $G$ containing the edge $e$.

For what set of edges does $\mathcal{C_e}$ contain a basis of the Cycle Subspace of $G$?

2

$\begingroup$
$\endgroup$

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