Equivalence relations on graphs Consider the graph $G$. For edges $e_1,e_2 \in E(G),$ let $e_1 \sim
e_2$ if either $e_1 = e_2$ or  $e_1$ and $e_2$ lie on some common cycle in
$G$. I want to be able to prove that $\sim$ is an equivalence relation.
It is apparent to me that by definition, $e \sim e$, and so reflexitivity holds.
If $e \sim e'$, the $e'$ must lie in the same cycle as $e$, so $e' \sim e$, and
thus symmetry holds. However, I am having some difficulty proving some
results related to transitivity. Say $e \sim e' \wedge e' \sim e''$. I want
to figure out a cycle that includes all three vertices. If we consider
the path $e,e',e'',$ how are we to be sure that there is some cycle that will
lead back to $e$? Any assistance would be appreciated.
 A: If either $e=e^\prime$ or $e^\prime=e^{\prime\prime}$ it is clear, so assume otherwise. If $e=e^{\prime\prime}$, then $e\sim e^{\prime\prime}$, so suppose all three edges are pairwise distinct.
The symmetric difference $C\triangle C^\prime$ of cycles is a collection of cycles (a proof).  
If $e$ and $e^{\prime\prime}$ lie in the same connected component of $C\triangle C^\prime$, then you have your cycle. From now on, suppose the edges are in different components $e\in E(G_1)$ and $e^{\prime\prime}\in E(G_2)$. 


*

*Look at $C\cap G_1$, which is a path $P$. Call its end vertices $v$ and $u$. 

*Now $C^\prime-G_1$ forms a path $P^\prime$ (in the original graph) from $u$ to $v$, and including $e^{\prime\prime}$, since $e^{\prime\prime}\notin G_1$.


The path $P\cup P^\prime$ includes $e$ and $e^{\prime\prime}$, and does not repeat any edges (it is the union of a path in $G_1$ from $v$ to $u$ plus a path outside of $G_1$ from $u$ to $v$); i.e. it is the desired cycle, and $e\sim e^{\prime\prime}$.

