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.
 A: 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?
A: 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 ;-)
A: 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.
