# Every $k$ vertices in an $k$ - connected graph are contained in a cycle.

Let $G$ be a $k$-connected graph. Meaning, $G$ has no less than $k$ vertices, and for every set of $k-1$ or less vertices, if we remove them from $G$, the graph stays connected (Of course, $G$ itself is also connected).

I want to prove that for any $k>1$, if $G$ is $k$-connected, then every set of $k$ vertices is contained in a cycle.

I have tried some ways - mainly using induction by removing one of the vertices of the set from the graph, and/or using Menger's theorem to construct the cycle. But I always encounter problems with making sure that the cycle I'm building deosn't have repeating edges etc.

Help would be greatly appreciated :) Thanks!

-
Won't you have to allow the cycle to have repeated edges? Otherwise how could a vertex of degree one be in a cycle? –  Tara B Jun 9 '12 at 13:17
@TaraB: A $2$-connected graph has no vertices of degree $1$. –  Chris Eagle Jun 9 '12 at 13:30
@Chris: Yes, thanks, I had just realised that and was about to delete my comment. –  Tara B Jun 9 '12 at 13:33

Take a cycle $C$ containing as many of the $k$ designated vertices as possible. If cycle has all the k designated vertices then you are done. Otherwise, By Menger's theorem , you can choose k paths from a missing vertex to the cycle $C$. The end points of the paths in $C$ divide $C$ into $k$ segments. One of the segments does not contain any of the designated vertices. Replace that segment by the two paths connecting the ends of the segment to the missing vertex.