The existence of a cycle in a graph Let $C$ and $D$ be different cycles in the graph $G$, and $e$ a common edge of cycles $C$ and $D$. Show that $G$ contains a cycle not passing through the $e$.
I think, it's not easy task, because graphs may be enmeshed.
 A: $C$ and $D$ are nonidentical cycles. So if $C$ and $D$ have $k$ edges in common, those edges cannot form a cycle, and so $C$ and $D$ must have at least $k+1$ vertices in common: namely, the vertices incident on those $k$ edges. So the subgraph $C \cup D - e$ has $|C|+|D|-k-1$ edges and at most $|C|+|D|-k-1$ vertices. Since it has at least as many edges as vertices, it cannot be a forest.
A: I came up with a solution and hope it's flawless.
It suffices to restrict $G$ to $V(C) \cup V(D)$ and $E(C) \cup E(D)$. As $C$ and $D$ are different cycles, there exists an edge in exactly one of them. WLOG, $\exists \space e' \in C, e' \notin D$. Let $e=uv$ be the shared edge between $C$ and $D$. Now define a new graph $S$ with the same vertex set as $V(C) \cup V(D)$ and all edges of $E(D) \backslash e$. It's obvious that $S$ is a forest. Now consider cycle $C$ and edge $e=uv$. Now consider $C\backslash e$ which is a path $P$ from $u$ to $v$. Move along this path from $u$ to $v$. At each movement along an edge $e$", if $e$" is a multiple edge in $S$ ignore it and otherwise add it to $S$. If it joins 2 vertices from the same component it creates a cycle and we're done, otherwise it merges 2 different components one of which is a single vertex and hence we'll have one non-trivial component at each step. We have $e' \in C$ and $e' \notin D$ so when we reach this edge, it won't be multiple edge and hence will be added to $S$. From this point on, consider the first vertex $w \in V(C) \cap V(D)$ which we reach along path $P$ and edge $l$, such vertex will always exist as $v$ is one. $l$ is between 2 vertices of the same component and is not a multiple edge hence adding it to $S$ creates a cycle and we're done. $\blacksquare$
Regards
