# 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

## 2 Answers

Here is a rough argument:

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.

-

It should be an induction statment, the induction is on k.

Base of induction begins with k=2 then we know every $u,v \in V$ have at least two vertex-disjoint paths (this is by Menger's theorem) $P_1=(v,...,u)$ and $P_2=(v,...,u)$ , we notice $P_1P_2$ is a cycle and u and v are both in it which means for every group |S|=k=2 it holds that it is contained in a cycle.

Induction hypothesis is that for k-1 - conectedness the statment holds, which means take any groups of vertices |S|=k-1 you'll have them sitting on a cycle C. So now it's left to take arbitary $v \in V$ in a k-connected graph remove it and this gives us a graph k-1 connected so a group |S|=k-1 sits on a circle and now it's only left to look at v-as suggested above using menger and creating a cycle.

-