# 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.

• There might not be a cycle that contains all of $e,e',e''$. You need to show that there's a cycle containing $e$ and $e''$. – kccu Jun 10 '16 at 0:50
• Note that union of cycle containing $e$ and $e'$ and cycle containing $e'$ and $e''$ is also cycle and it contains $e$ and $e''$. – Anton Grudkin Jun 10 '16 at 1:00
• @AntonGrudkin How so? Typically edges and vertices are not allowed to repeat in a cycle. – kccu Jun 10 '16 at 1:08
• @kccu Depends on what type of cycles we talk about - simple cycles or closed walks. For simple cycles the whole statemend is false: consider graph which contains only two simple cycles with one common vertex $e$. If $e'$ is vertex from one cycle and $e''$ --- from other one that $e' \sim e$ and $e' \sim e''$ but $e'\not\sim e''$ as the only cycle contains bouth verctices $e'$ and $e''$ has repition on vertex $e_0$ and it is not simle. – Anton Grudkin Jun 10 '16 at 1:16
• @AntonGrudkin The relation is on edges, not vertices. – kccu Jun 10 '16 at 1:24

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}$. • (+1) I took the liberty of adding two more images to help explain the text. – Brian M. Scott Jun 13 '16 at 21:40