3
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ What about removing all of the edges that are in the intersection of both cycles? Assuming the cycles are distinct, then this is still a cycle. This is the same as your idea of "using the cycle after the point of intersection". Additionally, if the cycles share a vertex, then you can continue following the 'new' cycle until you hit that vertex again. In which case you've found a new cycle which isn't necessarily the XOR sum of the original cycles (but is still a cycle!) since you've returned to the original spot again. $\endgroup$ – Guillermo Angeris Aug 24 '17 at 15:44
  • 2
    $\begingroup$ @GuillermoAngeris it is a good idea, but it is slightly more complicated than that. Taking the union of two cycles and removing all edges that are common to both may leave you with more than one cycle. Follow my mind for a moment... start with a big cycle on the left, and on the right you have a cycle that comes and shares an edge, leaves, comes back shares another edge, leaves, comes back and shares another few more edges, etc... and not even necessarily in a particular order or direction... $\endgroup$ – JMoravitz Aug 24 '17 at 15:50
  • 2
    $\begingroup$ Sure! I agree, you can definitely have multiple cycles formed by the construction, but you only need to construct one such cycle and you know that the number of edges are finite and that the degree of each vertex is even. So, you must end back on an edge that you've crossed previously if you continue along the path. Perhaps more rigorously, this construction yields components, all of which have Eulerian cycles since each vertex has even degree. $\endgroup$ – Guillermo Angeris Aug 24 '17 at 15:58
  • 1
    $\begingroup$ @GuillermoAngeris I like your idea to generate at least one cycle by removing all shared edges of the original pair of cycles. I'm fairly certain that it works, but how do you prove it? I don't have much experience with proofs in graph theory, I don't really know how they work ... $\endgroup$ – Zubin Mukerjee Aug 24 '17 at 16:17
  • 1
    $\begingroup$ Maybe induction on the number of vertices in the graph? I don't think that would work, since there are so many possibilities for which edges exist between the new ($n+1^{\text{th}}$) vertex and the $n$ old vertices ... $\endgroup$ – Zubin Mukerjee Aug 24 '17 at 16:17
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What if the second cycle intersects the first cycle in more edges than just $e$? I'm not sure this proof works in that case ... also, it seems very non-rigorous to appeal to intuition ("from the other side", "backtrack", etc.) in the proof, but I am not too familiar with proofs in graph theory, so that could be standard? Edit: it's possible I've just misunderstood the proof $\endgroup$ – Zubin Mukerjee Aug 24 '17 at 16:21
  • 1
    $\begingroup$ @ZubinMukerjee The proof does work in that case. The point is that because we have a non-backtracking walk (i.e. at no point to we go $v_1,v_2,v_1$) we can only repeat a vertex if we encounter a cycle. I don't know the standard terminology, but I know that an argument like this is used in L,P,V's Discrete Mathematics text to show that every tree has a leaf. $\endgroup$ – Omnomnomnom Aug 24 '17 at 16:33

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.