# Cycles in $k$-connected graphs

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?

-

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.

-
Why does deleting $C$ leave a connected graph? – Chris Eagle Jan 8 '11 at 3:35
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. – Xiaochuan Jan 8 '11 at 7:45

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.

-

Seems like another application of Dirac's Theorem.

-