# Prove a graph with $2n-2$ edges has two cycles of equal length

I’m trying to solve the following question:

Let $G$ be graph on $n ≥ 4$ vertices with $2n − 2$ edges. Prove that $G$ has
two cycles of equal length.

I have reached the following observations:

1. If I try and prove this by induction, during the induction step I have a graph of n vertices and if I remove the minimal-degree vertex it’s easy to see that if it has 2 or less edges, then the resulting graph is a graph of n-1 vertices and at least 2(n-1)-2 edges, so by the induction assumption there are two cycles of equal length. However I still need to prove that if the minimal degree in the original n-vertices graph is larger than 2, then this means it is still possible to find two equal length cycles (it’s no longer possible to remove a vertex and keep the required amount of edges).
2. If a graph has a minimal degree of 3, then it has a cycle with a chord – perhaps this could help me here, alongside with the induction idea?
3. If the minimal degree is 3 I believe this means that there must be a cycle of length 4 (at least one). Maybe it’s possible to look at this cycle and do something with it (maybe removing it…?)

Any help would be appreciated as I am currently a bit stuck.

#### Solutions Collecting From Web of "Prove a graph with $2n-2$ edges has two cycles of equal length"

Consider a spanning tree of the graph (or a spanning forest, the argument works analogously). The longest path of any tree is at most $n-1$ steps. Then when we add edges to a tree, we join vertices which have a distance of $2 \le d \le n-1$ between them. There are $n-2$ such distances and we must add at least $2n-2 – (n-1) = n-1$ edges. Therefore by the pigeon-hole principle, one distance $d$ must be repeated. This means that the graph has two cycles of length $d+1$.