For $n\ge4$, let G be a simple n-vertex graph with at least $2n - 3$ edges. Prove that G has two cycles of equal length. (West's Introduction to Graph Theory Q 2.1.42)
I am trying to prove the above claim. So far I have reasoned as follows:
G must be connected because $2n-3\ge n-1$ for $n\ge4$, and any simple n-vertex graph with at least $n-1$ edges must be connected.
Let T be a spanning tree of G. T must have $n-1$ edges. Therefore T has at least $2n-3 - (n-1) = n-2$ fewer edges than G. That is, $|e(G) \setminus e(T)| \ge n-2$.
Each one of these 'extra' edges adds exactly cycle to G, so G has at least $n-1$ cycles, each with length 3 to n.
Because there are at least n-2 cycles in G, it suffices to show that $n-2$ of these edges cannot all have distinct sizes. (I'm unsure about this line... is this a correct statement?)
From here I've lost my way, but I think I am on the right track. For what it's worth, this question appears right after the section that introduces trees, spanning trees, and their properties etc.
Thank you!
You are almost done. There are at least $n-1$ cycles, each of them has a size from 3 to $n$ ($n-2$ possibilities) so at least two of them have the same size (pigeonhole principle).