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:
Any help would be appreciated as I am currently a bit stuck.
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$.