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.

I'm trying to solve the following question:

Let $G$ be graph on $n ≥ 4$ vertices with $2n − 2$ edges. Prove that $G$ has two cycles of equal length.

I have reached the following observations:

  1. If I try and prove this by induction, during the induction step I have a graph of n vertices and if I remove the minimal-degree vertex it's easy to see that if it has 2 or less edges, then the resulting graph is a graph of n-1 vertices and at least 2(n-1)-2 edges, so by the induction assumption there are two cycles of equal length. However I still need to prove that if the minimal degree in the original n-vertices graph is larger than 2, then this means it is still possible to find two equal length cycles (it's no longer possible to remove a vertex and keep the required amount of edges).
  2. If a graph has a minimal degree of 3, then it has a cycle with a chord - perhaps this could help me here, alongside with the induction idea?
  3. If the minimal degree is 3 I believe this means that there must be a cycle of length 4 (at least one). Maybe it's possible to look at this cycle and do something with it (maybe removing it...?)

Any help would be appreciated as I am currently a bit stuck.

share|improve this question
    
The result holds even if the number of edges is $2n-3$. –  caffeinemachine Jun 17 at 5:26

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
Note that $n\ge 4$ was not used in this proof (but $n>1$ was used - where?). Of course, for $n=3$ and $n=2$ the claim is trivially true. –  Hagen von Eitzen Nov 28 '12 at 21:42
    
@HagenvonEitzen I think $n \ge 4$ is implicitly needed. You can't have $2n-2$ edges for $n < 4$ vertices. –  EuYu Nov 28 '12 at 21:53
    
That's exactly why it is not needed :) All you need is that the spanning tree is not just a point, so that the number of distances $d$ with $2\le d\le n-1$ is indeed $n-2$. –  Hagen von Eitzen Nov 28 '12 at 23:26
    
It might be worth adding that for non connected graph, this proof still holds as there is a connected component with $k$ vertices and $2k-2$ edges, because the ratio edges/vertices of the entire graph is $2n-2/n$ so if we have a connectivity component below this ratio, there must be another above it. –  Uri Jan 7 '13 at 18:39

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.