Take the 2-minute tour ×
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.

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|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

1 Answer 1

up vote 1 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|improve this answer

Your Answer

 
discard

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.