Ore's theorem

Statement

Let $G$ be a finite simple graph with $n \ge 3$ vertices. Suppose that $\deg(u) + \deg(v) \ge n$ for any two distinct vertices $u$ and $v$ that are not adjacent. Then $G$ is Hamiltonian.

Remarks

Dirac's theorem is a special case. The Bondy–Chvátal theorem of 1976 extends it. It says that $G$ is Hamiltonian if and only if its closure is Hamiltonian. The closure comes from $G$ when you add edges $uv$ with $\deg(u) + \deg(v) \ge n$ again and again.

History

Øystein Ore proved the theorem in 1960.

Explanations

L1 human

Ore's theorem looks only at pairs of vertices that are not neighbours. If each such pair has many edges together, the graph has a round trip through all vertices.