path from a to b containing k vertices

Question

Let $G$ be a $k+1$ connected graph with distinct vertices $a, b, x_1, ... , x_k$. Show that there is a path from $a$ to $b$ containing all the $x_i$.

My idea was to use Menger's theorem on the neighbours of $a$ and $b$. This means that from any neighbour of $a$ there are $k+1$ vertex disjoint paths to every neighbour of $b$.

But I also need to make sure that all the $x_i$ are contained. Can anyone give me a hint?

Answer 1

Hint: you may find the Fan Lemma useful. It says that in a $k$-connected graph, if you have vertices $u, v_1, v_2,\dots, v_k$, then exists a family of $k$ internally disjoint disjoint paths $P_1, P_2, \dots, P_k$, where the path $P_i$ starts at $u$ and ends at $v_i$.

A proof can be found here: A question on $k$-connected graphs. (hover over the boxes to see more hints)

To prove the fan lemma, you attach an extra vertex $w$ to all the $v_i$ and then use Menger's to get $k$ internally disjoint $u-w$ paths.

Proof idea using Fan Lemma:

Among all the $a-b$ paths in $G$, pick $P$ to be one that contains the maximum number of the vertices $x_1, x_2, \dots, x_k$. If it has them all, you're done. So assume $P$ does not have, say, $x_k$. Since $G$ is $k+1$-connected, there's $k+1$ internally disjoint paths that all start at $x_k$ and end at a different vertex in $a,b, x_1, \dots, x_{k-1}$ by the Fan Lemma. By looking at how these paths intersect the segments of the path $P$, and by using the pigeon-hole principle, you can show that you can make a path from $P$ that contains all the same vertices as well as $x_k$, contradicting maximality of $P$.

This is very similar to the proof of Dirac's Theorem, which you can find here: Every $k$ vertices in a $k$-connected graph lie on a cycle