# Graph theory: cycles

Prove that if two distinct cycles of a graph $G$ each contain an edge $e$, then $G$ has a cycle that does not contain $e$.

My approach is since they both have edge e then if we remove edge $e$ from both then connect the two cycles together at vertex $a$ and $b$ which edge $e$ connected to then we would get a cycle. Am I missing something here?

This isn't a homework question, just a question from my textbook.

-
I figured I would note that the cycle space is a vector space. In particular, it is a subspace of edge space. The vectors are edge sets, with the finite field $\{0, 1\}$ and addition as the symmetric difference. In cycle space, the edge sets all form cycles, save for the empty set. Since cycle is closed under addition, we have that the symmetric difference of two cycles yields a cycle in the graph. – ml0105 Mar 18 '14 at 4:16

Another approach would be to take the connected component that contains both cycles and observe that in this subgraph $|E| \geq |V|+1$. To be more explicit:

• $|E| \leq |V|-2$ the graph would not be connected,
• $|E| = |V|-1$ the graph would be a tree (no cycles),
• $|E| = |V|$ the graph would have exactly one cycle,
• $|E| \geq |V| + 1$ is the only possibility.

Then if we remove $e$, we have $|E - \{e\}| \geq |V|$ which still implies the existence of some cycle, which, of course, cannot contain $e$ (it is not necessary, but if you wonder, this connected component is still connected because $e$ was an edge of a cycle).

I hope this helps ;-)

-

The idea is correct. The problem comes when the two cycles have other edge in common beyond 'e'. How do you manage that case? Do you need to use the hypothesys that the two cycles are distinct?

-
The question states distinct cycles. – DJ_ Feb 3 '13 at 7:47
Distinct cycles may contain more than one edge in common, so long as they don't contain all their edges in common. – Steve Kass Feb 3 '13 at 7:49

I think it's quite straightforward to see. Imagine to cycles $C_n$ and $C_m$ that they share a common vertex $e$. If you erase this edge, you still will have that both cycles coincide in exactly 2 vertices. There you have the cycle.

-