11
$\begingroup$

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.

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

1 Answer 1

8
$\begingroup$

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

$\endgroup$
4
  • $\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, 2012 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, 2012 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, 2012 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, 2013 at 18:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .