A question on $k$-connected graphs I'm looking for a proof of this theorem by Dirac:
If a graph is $k$-connected for $k \ge 2$, then for every set of $k$ vertices in the graph there is a cycle that passes through all the vertices in the set.
I know a proof probably uses Menger's theorem but I haven't been able to find one or come up with one.
 A: Prove Dirac's fan lemma first:
If $G$ is a $k$-connected graph $x$ a vertex, and $V$ a set of $n\geq k$ vertices then there exists a family of $k$ vertex disjoint paths (disjoint except for vertex $x$) from $x$ to $k$ of the $n$ vertices (all of them distinct,thanks to the fact they are vertex disjoint)
To prove this just add a vertex $y$ that is connected to each of the vertices on $V$, this gives us a $k$ connected graph as the reader should verify. By Menger there are $k$ vertex disjoint paths from $x$ to $y$. When we remove $y$ from each of these paths we obtain the $k$ paths that are necessary for the fan lemma.
We now use the Fan lemma along with induction to prove the claim.
The base case is when $k$ is $2$-connected. We have to prove given $x$ and $y$ there is a cycle containing them This is just simple Menger. By Menger there are two vertex disjoint paths between $x$ and $y$, the union of these paths is a cycle.
Take the set of $k$ vertices $v_1,v_2\dots v_k$ and remove $v_k$. We get a graph that is $k-1$ connected so by the induction hypothesis  there is a cycle that contains $v_1,v_2\dots v_{k-1}$ If this cycle also includes $v_k$ we are done, otherwise we need to use the fan lemma.
Case $1$: The cycle that we extracted contains exactly the vertices $v_1,v_2\dots v_{k-1}$ and no others. The use the fan lemma to find $k-1$ vertex disjoint paths from $x$ to each of the other vertices. Then all we do is take the path from $v_k$ to $v_1$ and then go around the cycle to $v_{k-1}$ and the take the path from $v_{k-1}$ to $v_k$ to obtain a cycle containing all the vertices.
Case $2$: The cycle contains other vertices. In this case we apply the fan lemma to obtain $k$ paths from $v_k$ to the cycle ,notice that we can take these paths so that they only touch the cycle once (if they touch it twice just cut the path so it ends at the first vertex of the cycle). Now notice that the vertices $v_1,v_2\dots v_{k-1}$ split the cycle into $k-1$ segments. However we have $k$ paths from $v_k$ to the cycle, so two of these paths must go inside the same segment (suppose they end in $a$ and $b$. Now all we have to do is start at $v_k$ and go to vertex $a$, after that go around the cycle touching every vertex in the set $v_1,v_2\dots v_{k-1}$ until you get back to $b$. After this go back from $b$ to $v_k$ using the path. This gives us the desired cycle.
If I recall correctly you can find this solution in Bondy's graph theory text also.
