# 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
*h*_{1}c_{1},
*h*_{2}c_{2},
*h*_{3}c_{3},
with *h*_{i} in *V(H)*,
*c*_{i} in *V(C)* and with
*h*_{1},
*h*_{2},
*h*_{3},
*c*_{1},
*c*_{2},
*c*_{3}
all distinct.
Let *n*_{i} denote the number of edges
from *h*_{i} to
*V(C)*. We may assume that
*n*_{1} is as large as possible.
By the lemma briefly mentioned,
there is a path of length at least
*d-n*_{1} between any pair chosen from
*{h*_{1},h_{2},h_{3}}.
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=w*_{0}w_{1}...w_{n}, with
*w*_{0}=u, *w*_{n}=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,
*w*_{i+1} is in *T* if and only if
*w*_{i} is a neighbour of *v*.
But, *|S|+|T|* is at least *|V(G)|*,
and therefore
there is a vertex *w*_{i+1} in both
*S* and *T*. But then
*C[w*_{0},w_{i}] union
*C[w*_{i+1},w_{n}] union
*{w*_{0}w_{i+1},w_{i}w_{n}}
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.