Ore's Theorem

Theorem

Let $G = \left({V, E}\right)$ be a simple graph of order $n \ge 3$ which is connected.

Suppose $G$ fulfils the following condition:

For each pair of non-adjacent vertices $u, v \in V$, $\deg u + \deg v \ge n \qquad (1)$.

Then $G$ is Hamiltonian.

Proof

Suppose it were possible to construct a graph that fulfils condition $(1)$ which is not Hamiltonian.

For a given $n \ge 3$, let $G$ be the graph with the most possible edges such that $G$ is non-Hamiltonian which satisfies $(1)$.

Although it does not contain a Hamilton cycle, $G$ has to contain a Hamiltonian path $\left({v_1, v_2, \ldots, v_n}\right)$.

Otherwise it would be possible to add further edges to $G$ without making $G$ Hamiltonian.

Since $G$ is not Hamiltonian, $v_1$ is not adjacent to $v_n$, otherwise $\left({v_1, v_2, \ldots, v_n, v_1}\right)$ would be a Hamilton cycle.

By $(1)$, we have that $\deg v_1 + \deg v_n \ge n$.

By the Pigeonhole Principle, for some $i$ such that $2 \le i \le n - 1$, $v_i$ is adjacent to $v_1$, and $v_{i-1}$ is adjacent to $v_n$.

But the cycle $\left({v_1, v_2, \ldots, v_{i-1}, v_n, v_{n-1}, \ldots, v_i, v_1}\right)$ is then a Hamilton cycle.

So $G$ is Hamiltonian after all.

$\blacksquare$

Note

Not all Hamiltonian graphs fulfil the condition $\deg v_1 + \deg v_n \ge n$.

For example, the cycle graphs $C_n$ where $n \ge 5$ are all such graphs.

Also see

Dirac's Theorem

Source of Name

This entry was named for Øystein Ore‎.

It was demonstrated in 1960.