Show that if G is a simple graph with at least 4 vertices and 2n-3 edges, it must have two cycles of the same length.

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!

Solution 1:

Jernej is correct, $|V(G)| = n$ and $|E(G)|=2n-3$ does not imply that $G$ is connected. Counter example: Consider $n = 6$, then $2n-3=9$. You can construct a graph consisting of a single isolated node and an almost completely connected component with 5 vertices. This is possible because $|E(K_5)| = 10 > 9$.

WLOG let $G$ have $k$ connected components $c_i$, $i=1,\dots,k$. Let $c_j$ be such that $|V(c_j)| \geq 4$ and $|E(c_j)| \geq 2\cdot|V(c_j)| - 3$. Such a $c_j$ must exist because $G$ could not have $2n-3$ edges otherwise. Now consider $T$, the spanning tree of $c_j$. It consists of $|V(c_j)| - 1$ edges, so there are at least $|V(c_j)| - 2$ edges left. Each of these edges creates a cycle of length between 3 and $|V(c_j)|$ when joined with $T$. Since there are $|V(c_j)| - 2$ edges and $|V(c_j)| - 2$ possible distinct cycle lengths this is not yet enough to apply the pigeon hole principle. However, observe that when there is a cycle of length $|V(c_j)|$ every additional edge will create at least two new cycles. Hence either there will be a repeated cycle length when choosing $|V(c_j)|-2$ lengths with $|V(c_j)|-2$ edges, or if not, then there must be a cycle of length $|V(c_j)|$ and so there will be $2(|V(c_j)|-3)+1$ cycles. $2(|V(c_j)|-3)+1$ > $|V(c_j)|-2$ for all $|V(c_j)| > 3$ so the pigeon hole principle can be applied in this case. $\quad\square$

Solution 2:

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