Understanding the Proof of Dirac's Theorem Regarding Graph Connectivity

Question

In Introduction to Graph Theory, the authors state the following theorem attributed to Gabriel Dirac:

If G is a k-connected graph, $k\ge2$, then every k vertices of G lie on a common cycle of G.

and give the following proof:

Let $S=\left\lbrace v_{1},v_{2},\ldots v_{k}\right\rbrace $ be a set of $k$ vertices of $G$. We show that there exists a cycle in $G$ containing all the vertices of $S$. Among all cycles in $G$, let $C$ be one containing a maximum number $l$ of vertices of $S$. We claim that $l=k$. Assume, to the contrary, that $l < k$. Since $G$ is $k$-connected and $k \ge 2$, it follows that $G$ is 2-connected and so $2 \le l < k$. We may assume that $C$ contains the vertices $v_{1},v_{2},\ldots,v_{l}$ of $S$ and that the vertices of $S$ on $C$ appear in the order $v_{1},v_{2},\ldots,v_{l}$ as we proceed cyclically about $C$. In particular, there is a $v_{1} - v_{2}$ path $P$ on $C$ that contains no internal vertices belonging to $S$. Since $l <k$, there is a vertex $u \in S$ that does not belong to $C$. Furthermore, since $2 \le l < k$, the graph $G$ is $l$-connected as well. Thus, $G$ contains internally disjoint $u-v_{i}$ paths $P_{i}$ ($1\le i \le l$). Replacing $P$ by $P_{1}$ and $P_{2}$ produces a cycle $C'$ containing the vertices $u,v_{1},v_{2},\ldots,v_{l}$, a contadiction.

I am having trouble with this proof because although I understand that $P_{1}$ and $P_{2}$ do not contain any of the vertices $v_{3},\ldots,v_{l}$, it seems to me that these paths may very well contain other vertices of $C$ in which case it is not at all obvious to me how $C'$ is obtained.

Is the proof lacking or am I simply not getting it?

Answer 1

I think you're right, this is a gap in the proof. It seems that the authors later realized this; in the fifth edition of their book Graphs & Digraphs (which is from 2010), they give a correct proof using a case distinction and, implicitly, the pigeonhole principle. A similar proof without the explicit case distinction is given here. The basic idea is that there are internally disjoint paths from $u$ to $\min(|C|,k)$ points on $C$, and by the pigeonhole principle the vertices at which they first meet $C$ can't all lie on different ones of the $l$ segments formed by $v_1,\dotsc,v_l$, so there's at least one pair that you can use to splice in $u$.