Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.