Dirac's theorem
From Wikipedia, the free encyclopedia
In graph theory, there are two theorems that are commonly referred to as Dirac's theorem, both named after the mathematician Gabriel Andrew Dirac:
- Let G be a k-connected graph. Then for any set of k vertices in G, there exists a cycle in G that passes through all k vertices.
- Let G be a graph on n ≥ 3 vertices. If each vertex has degree at least n/2 then G is hamiltonian.