Graph with edge disjoint cycles

3.2k Views Asked by At

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

There are 1 best solutions below

1
On

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