4
$\begingroup$

I was reading "Graph Theory" by Diestel and I tried to solve a problem from the chapter 3 (on connectivity). It seems at first sight easy (and really intuitive) but I have to admit that I can't work it out! Here is the problem: prove that every $k$-connected graph of order at least $2k$ contains a cycle of length at least $2k$.

Does anyone have a suggestion?

3 Answers 3

2

Seems like another application of Dirac's Theorem.

5

Consider the longest cycle $C$ in $G$ and suppose its length is less than $2k$. Use Menger's Theorem and the pigeonhole principle to come up with a contradiction.

3

First suppose for contradiction that the length of the longest cycle $C$ is $2k-1$. Then consider the set of vertices in $C$, which are connected with vertices outside $C$. It has cardinality at least $k$. Otherwise, by deleting these vertices, the graph left is still connected.

Then by pigeonhole principle there are two adjacent verticies $A$ and A' in $C$, which are connected with vertices outside $C$, say, $B$ and B'.

The situation when B=B' automatically makes a longer cycle. When $B$ and B' are different, we delete $C$, and get a connected graph. We connect $B$ and B', using vertices all outside $C$. This makes the cycle longer.

  • 0
    Sorry I was not clear. Suppose $C^c$ is not connected. Specificly, $B$ and $B'$ can't be connected by any path within $C^c$. In another word, every path connecting $B$ and $B'$ must go through $C$. By Menger's Theorem, we have that there are at least $k$ disjoint paths connecting $B$ and $B'$. So we have two disjoint paths connecting $B$ to the cycle C, which make our cycle longer.2011-01-08