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:

  1. 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.
  2. Let G be a graph on n ≥ 3 vertices. If each vertex has degree at least n/2 then G is hamiltonian.