# 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!

• The claim that a simple graph of order $n$ and at least $n-1$ edges iimplies that $G$ is connected is wrong. – Jernej Mar 3 '14 at 19:55

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