Dirac's Theorems

Theorem 1. Let G be a 2-connected graph with minimum degree d. Then G contains a cycle of length at least min{2d,|V(G)|}.

Proof.
Theorem 2. Let G be a k-connected graph, k>1. Then any k vertices of G are contained together on some cycle.

Proof.
For a few extensions see Egawa, Glas, Locke and Locke, Zhang
Proof of Theorem 1. This is normally split into two cases.

Case 1. Suppose, first, that 2d is at least |V(G)|. Then, we need to show that G has a Hamilton cycle. The nicest proof I've seen for this case uses a method due to Bondy and Chvátal.

Lemma (Bondy and Chvátal). Let u and v be two nonadjacent vertices of G such that degree(u)+degree(v) >= |V(G), then G is hamiltonian if and only if G+uv is. Proof of Lemma.

To complete the proof that G is hamiltonian if 2d is at least |V(G)| we note that for a graph with this condition, repeated application of the Lemma will produce a complete graph (which is obviously hamiltonian). Therefore, each of the graphs produced in the sequence leading to that complete graph must be hamiltonian, including G.

Case 2. Now, we may assume that 2d<|V(G)|. let C be a longest cycle in G. I will only give a very rough sketch of the proof of this case.
Suppose that |V(C)| < 2d. Then G-V(C) must have at least one (non-empty) component H. We now consider a long path P in H and edges connecting the ends of P to C.

When I do it this way, I usually break this into four subcases, all of which are handled by similar techniques: (i) |V(H)| = 1; (ii) |V(H)| = 2; (iii) H is 2-connected with at least three vertices; (iv) H is separable. Also, I need a little lemma that says that a 2-connected graph with minimum degree d must contain a path of length at least d between any given pair of vertices. (I can even allow one vertex to have degree less than d.)

Subcase (i). There are at least d edges from H to V(C), and no two of these end at consecutive vertices of C. Thus, C must have length at least 2d.

Subcase (ii). There are at least 2d-2 edges from V(H) to V(C), ending with at least d-1 distinct vertices of C. These vertices of C partition C into edge-disjoint paths, which I will call subpaths. Furthermore, no two of these vertices of C can be consecutive on C. That is, each subpath must have length at least two. Nor can edges from distinct vertices of H end at vertices whose distance on C is two and, therefore, there must be two subpaths of C which length of at least three. Thus, C must have length at least 2d.

Subcase (iii). There are at least three edges h1c1, h2c2, h3c3, with hi in V(H), ci in V(C) and with h1, h2, h3, c1, c2, c3 all distinct. Let ni denote the number of edges from hi to V(C). We may assume that n1 is as large as possible. By the lemma briefly mentioned, there is a path of length at least d-n1 between any pair chosen from {h1,h2,h3}. A little simple and careful counting shows that C must have length at least 2d.

Subcase (iv). Here we need only pick one interior vertex from each of two distinct endblocks. We choose these two vertices to each have maximum number of neighbours on C. (It might happen that you can't quite do this, but then there must be some vertex which is not of this type and has a neighbour on C -- use it instead of one of the endvertices.) There must be a long path between the two vertices chosen, and the rest is simple and careful counting.
Lemma (Bondy and Chvátal). Let u and v be two nonadjacent vertices of G such that degree(u)+degree(v) >= |V(G), then G is hamiltonian if and only if G+uv is.

Proof of Lemma. Obviously if G is hamiltonian then G+uv is.

Now assume that G+uv is hamiltonian. Obviously, if G has a Hamilton cycle, we are done. Thus, we may assume that G has no Hamilton cycle and, therefore, G has a Hamilton path P=w0w1...wn, with w0=u, wn=v and n=|V(G)|. Let S be the set of neighbours of u, which are necessarily on P, and let T be the set of vertices on P which follow neighbours of v on P. That is, wi+1 is in T if and only if wi is a neighbour of v. But, |S|+|T| is at least |V(G)|, and therefore there is a vertex wi+1 in both S and T. But then C[w0,wi] union C[wi+1,wn] union {w0wi+1,wiwn} is a Hamilton cycle of G. Return to Proof of Theorem 1.
Proof of Theorem 2. This follows easily from Menger's Theorem and induction.

Let X be a set of k vertices in G.

Let C be a cycle that contains as many of the vertices of X as possible. Suppose that v is a vertex of X that is not on C. The vertices of X which are on C partition C into pairwise-internally-disjoint segments (which are paths if at least two vertices of X are on C.

By an easy extension of Menger's Theorem, there are at least min{k,|V(C)} paths from v to V(C) such that no two of these paths intersect, except at v. Therefore, there must be some pair of paths P, Q from v to V(C), disjoint, except at v, such that both paths end in the same segment of C. That is, P meets C at p, and Q meets C at q, where C[q,p] contains all of the vertices of X which are on C. But then, C' = P union Q union C[q,p] is a cycle that contains one more vertex of X than C does, contradicting the choice of C.
Last modified July 28, 1998, by S.C. Locke. How to contact me.