Dirac's Theorem

Theorem

If a connected graph $G$ has $n \ge 3$ vertices and the degree of each vertex is at least $\dfrac n 2$, then $G$ is Hamiltonian.

Proof

Take any two non-adjacent vertices $u, v \in G$.

Then:

$\displaystyle \deg u + \deg v \ge \frac n 2 + \frac n 2 = n$

The result follows by a direct application of Ore's Theorem.

$\blacksquare$

Source of Name

This entry was named for Gabriel Andrew Dirac.

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 3.2$: Theorem $3.4$