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.

  • $\begingroup$ The result holds even if the number of edges is $2n-3$. $\endgroup$ Jun 17 '14 at 5:26

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

  • $\begingroup$ 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. $\endgroup$ Nov 28 '12 at 21:42
  • $\begingroup$ @HagenvonEitzen I think $n \ge 4$ is implicitly needed. You can't have $2n-2$ edges for $n < 4$ vertices. $\endgroup$
    – EuYu
    Nov 28 '12 at 21:53
  • $\begingroup$ 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$. $\endgroup$ Nov 28 '12 at 23:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – Uri
    Jan 7 '13 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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