3
$\begingroup$

Let $G$ be a $k$-connected graph. Meaning, $G$ has no fewer than $k$ vertices, and for every set of $k-1$ or fewer 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!

  • 0
    Won't you have to allow the cycle to have repeated edges? Otherwise how could a vertex of degree one be in a cycle?2012-06-09
  • 0
    @TaraB: A $2$-connected graph has no vertices of degree $1$.2012-06-09
  • 0
    @Chris: Yes, thanks, I had just realised that and was about to delete my comment.2012-06-09

2 Answers 2

3

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.

  • 0
    What if there are two vertices v1,v2 not in C and we replace missing segment of C with path contaning v1 and in the next step for v2, the segment containing v1 is demanded to be replaced?2016-11-18
  • 0
    Remember that the segment you replace does not contain any of the designated vertices. That is the key point of the proof.2016-11-23
  • 0
    yes .. I got it .. for some reason I have misread the proof :)2016-11-23
  • 1
    Should'nt you mention that we need C to have at least k vertices? How can it be shown?2017-02-21
1

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.