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.