If the vertices of graph have a degree of at least $n\geq2$, show that the graph has at least $\frac{n}{2}$ edge disjoint cycles.

Unsure how to approach this, but I understand that edge disjoint cycles are cycles within a graph that don't have the same edge.

  • 1
    $\begingroup$ I think you mean it has at least $\lfloor \frac{n}{2} \rfloor$ disjoint cycles since for example: a $K_4$ doesn't have at least 1.5 disjoint cycles. $\endgroup$ – Jorge Fernández Hidalgo Jul 7 '14 at 2:19

Before you do anything, note that the graph must be finite. If the graph weren't finite, a trivial example of a graph with every vertex of degree $2$ without any cycle would be the integer line, where every point is labelled with an integer and each point $n$ would be connected to points $n+1$ and $n-1$.

With that out of the way, it's mostly a matter of actually drawing out these edge-disjoint cycles.

We can use induction. Let $G$ be a finite graph where every vertex is of degree at least $2$. Then, pick any vertex $v_0$, and starting from that vertex, trace a path through the vertices $v_1, v_2, v_3, \ldots$. If at any point along this path we reach a vertex $v_n$ that we already passed earlier in the path, we have a cycle and we're done. But supposing we'd never visited $v_n$ before, then only one edge on $v_n$ is part of the path, and therefore we can continue drawing the path by the another edge on $v_n$ since the degree of $v_n$ is at least 2.

Continue until you do get a vertex that's already in the path – because the graph is finite, this will happen eventually by the pigeonhole principle.

Now that we've proven that, do you see how to approach the problem when each vertex is of degree at least $2n$?

  • $\begingroup$ I understand that this isn't a complete answer, but I'm not sure if you're doing this as a homework question or not. I will fill in the rest eventually. $\endgroup$ – Joe Z. Jul 7 '14 at 1:49

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.