# Graph with edge disjoint cycles

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.

• 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. – 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$.
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.
Now that we've proven that, do you see how to approach the problem when each vertex is of degree at least $2n$?