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
    @Chris: Yes, thanks, I had just realised that and was about to delete my comment.2012-06-09

2 Answers 2

5

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.

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