Lesson 6

A direct consequence is Dirac's theorem.

Theorem (Dirac, 1952). If the degree of any vertex of an undirected graph is at least \(\frac{n-1}{2}\), then the graph has a Hamiltonian path. If the degree is at least \(\frac{n}{2}\), then there is also a Hamiltonian cycle.