3
$\begingroup$

Note: This is not an assignment/homework question, just review for an exam

We call two cycles edge-disjoint if they do not share any common edges, but they may share vertices.

Prove that any 4-regular graph contains at least two edge-disjoint cycles.

I was thinking that I could just choose two cycles, and allow them to share some vertex in order to complete the proof. But I only know that there is a single cycle in a 4-regular graph from the theorem that:

If every vertex has degree 2 or greater, then the graph contains a cycle.

I'm unclear of where to proceed.

$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

If every vertex has degree 2 or greater, then the graph contains a cycle.

If graph contains a cycle then this graph contains simple cycle. Now remove all edges of a simple cycle. Remaining graph has vertices of degree 2 and 4 only. Just apply this theorem once again.

$\endgroup$
6
  • $\begingroup$ I'm a little confused as to why this would help. Just because I removed edges of the cycle from the graph, how does that show that two cycles would share some vertex? Nothing guarantees that at the end of the day, that there are at least two cycles left. Also, what is the idea behind removing the edges in the cycle? $\endgroup$
    – efxgamer
    Feb 28, 2017 at 14:33
  • $\begingroup$ also, one more comment, why is that the remaining graph only has vertices of degree 2 and 4 only? Thanks for your help! $\endgroup$
    – efxgamer
    Feb 28, 2017 at 14:42
  • $\begingroup$ After getting the second cycle just restore removed edges to reconstruct the first cycle that has no common edges with the second one, as required. Edge-disjoint cycles may share, but not have to share vertices. $\endgroup$
    – Smylic
    Feb 28, 2017 at 14:42
  • $\begingroup$ If has vertices of degree 2 and 4 because for each vertex we removed 0 or 2 edges incident to this vertex. $\endgroup$
    – Smylic
    Feb 28, 2017 at 14:43
  • $\begingroup$ What guarantees that we are removing 0 or 2 edges? If we're just removing edges of a simple cycle, of which all vertices in the cycle have degree 4, whats to say that removing an edge won't just result in a vertex of degree 3? Thanks again really appreciate it. $\endgroup$
    – efxgamer
    Feb 28, 2017 at 15:01
2
$\begingroup$

Actually, any even-degree graph can be decomposed into edge-disjoint cycles via the algorithm:

  1. Pick a non-isolated vertex $v$ and go for a walk.

  2. The first time we see a repeated vertex $u$, then the sub-walk from $u$ back to itself identifies a cycle. Remove it from the graph.

    enter image description here

    In the above illustration, we'd remove the orange edges (ignoring the directions).

  3. If there are non-isolated vertices, go to Step 1. Otherwise, we have found a decomposition into cycles.

Since each vertex has even degree, it must be possible to continue walking until we revisit some vertex (otherwise there's a vertex of degree $1$). We also note the even-degree property does not change by removing a cycle.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .