I need to prove that if a graph $G$ has an edge $e$ contained in two different cycles, there exists a cycle that does not contain $e$.
I drew up an example on a graph, and it's clear to me that the cycles have to intersect at least once, and have at least one common edge ($e$). It occurred to me that then, we could use the other cycle after the point of intersection to return back to the original vertex.
However, what if the two cycles have more vertices in common? Then we would be going through one vertex twice (not a cycle).
So, is there merit in my idea, or how else would one prove that?
Best Answer
Suppose that the edge $e$ connects vertices $u$ and $v$. Construct a walk along the graph as follows: begin at $u$, traverse one cycle so that we end with $v,u$. To continue the walk, traverse the other cycle, but begin with $u,v$, and end the walk by coming to $u$ "from the other side".
There is exactly one section of the walk in which we redundantly follow a path to $u$ and then backtrack. If we remove this redundant piece of the walk, then we have now created a walk which ends where it begins and never goes back over the same edge it just crossed. This walk must, at some point, traverse a cycle, and at no point does it use the edge $e$.