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.

  • $\begingroup$ 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''$. $\endgroup$ – kccu Jun 10 '16 at 0:50
  • $\begingroup$ Note that union of cycle containing $e$ and $e'$ and cycle containing $e'$ and $e''$ is also cycle and it contains $e$ and $e''$. $\endgroup$ – Anton Grudkin Jun 10 '16 at 1:00
  • $\begingroup$ @AntonGrudkin How so? Typically edges and vertices are not allowed to repeat in a cycle. $\endgroup$ – kccu Jun 10 '16 at 1:08
  • $\begingroup$ @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. $\endgroup$ – Anton Grudkin Jun 10 '16 at 1:16
  • $\begingroup$ @AntonGrudkin The relation is on edges, not vertices. $\endgroup$ – 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}$.

enter image description here

  • 1
    $\begingroup$ (+1) I took the liberty of adding two more images to help explain the text. $\endgroup$ – Brian M. Scott Jun 13 '16 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.