Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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 at 19:55

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
Thank you. I had just come back because I had realized that my solution was incorrect. Very thorough explaination! –  mb7744 Mar 17 at 23:45

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.