Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.