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

graph-theory

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

Related

How are more difficult proofs discovered?
Existence of geodesic on a compact Riemannian manifold
Two Steps away from the Hamilton Cycle
Find the maximum and minimum of $\sum_{i=1}^{n-1}x_ix_{i+1}$ subject to $\sum_{i=1}^nx_i^2=1$.
Good introductory books on primitive recursive functions
Show f is uniformly continuous on $(a,b)$ if it is continuous and $\lim\limits_{x\to a^+}f(x)$ and $\lim\limits_{x\to b^-}f(x)$ exist
Why does cross product tell us about clockwise or anti-clockwise rotation?
Sum of $\sum_{n=1}^\infty \frac{(-1)^n}{n^2+(n^2-1)^2}$
What can we say about $(I-AD)^{-1}$ if $D$ is a diagonal matrix?
If a theory has a countable $\omega$-saturated model does it need to have only countable many countable models?
Continuity on closed intervals - differentiability on open intervals
$\mathcal U$ Grothendieck universe. Is $\mathcal{P(U)}$ a model for NBG?