Every k-connected path has a cycle containing any set of k of the vertices. A number of questions have been asked on this problem. Here is the one with the most detailed answers. The probelm is to prove that a k-connected graph $G$ has a cycle conatining an arbitrary set $x_1,x_2...x_k$ of the vertices.
The proof involves considering a maximal cycle C containing a many as possible of the $x_i$. If C does not include all of them, say some $x_m$ is not in C, then choose k endpoints in the cycle so that they section the cycle C in order to have one section which does not include any of the $x_i$. By Menger's theorem, we can find vertex disjoint paths from $x_m$ to each of these endpoints, and slot the $x_m$ into the section which does not contain any other of the $x_i$. This seems all well and good....
However I am not entirely convinced. Suppose the paths to any endpoints you could choose for a section which does not contain any $x_i$, are not vertex disjoint from the rest of the cycle C. Menger's theorem only gives us that the paths from $x_m$ to the k endpoints in C are disjoint, and not that each path is also disjoint with the rest of the vertices in C! I can imagine that maybe it would be impossible to slot the vertex in as required, without slicing up the cycle C so that you never have a cycle containing all of the $x_i$ at once!
 A: You shouldn't get attached to where the endpoints in $C$ are, since any configuration of those endpoints can make things work.
Assume that you have a cycle $C$ containing $x_1, \dots, x_{m-1}$ but not $x_m$.
Say you chose vertices $a_1, a_2, \dots, a_k$ in $C$, and then found vertex-disjoint $x_m,a_i$-paths for $i=1, \dots, k$. If it turns out that the path from $x_m$ to $a_i$ actually first visits another vertex $b_i$ of $C$, then simply forget about the $b_i$-to-$a_i$ segment of the path, and just take the segment $x_m$ to $b_i$. Now you still have $k$ vertex-disjoint paths from $x_m$ to $C$, but the $i^{\text{th}}$ one is shorter.
Or to put it differently: we can argue, by Menger's theorem or by Dirac's fan lemma, that there is at least one collection of $k$ vertex-disjoint paths starting at $x_m$ with endpoints somewhere on $C$. Pick such a collection of paths with the shortest total length. Then none of the paths visit $C$ before arriving at their endpoint - otherwise, you could truncate such a path to make it even shorter.
Now the argument you're quoting works without any problems.
Relabel the endpoints of these paths as $c_1, c_2, \dots, c_k$ so that this is the order they appear in on the cycle $C$. These $k$ endpoints break $C$ up into $k$ segments, and one of the segments (say, from $c_{i-1}$ to $c_i$) does not contain any of $x_1, \dots, x_{m-1}$ (because that's at most $k-1$ vertices). Replace the segment from $c_{i-1}$ to $c_i$ by the path from $c_{i-1}$ to $x_m$ and the path from $x_m$ to $c_i$, and you've found a cycle containing all of $x_1, x_2, \dots, x_m$.
