Hamiltonian

A graph is said to be Hamiltonian iff it contains a Hamiltonian cycle. Introduced by William Hamilton in 1857, while studying cycles in the dodecahedron graph.

Dirac’s Theorem

A simple graph with $n \ge 3$ vertices is Hamiltonian if every vertex has degree at least $n/2$.

Ore’s Theorem

A simple graph with $n \ge 3$ vertices is Hamiltonian if for every pair of non-adjacent vertices $u$ and $v$: