Ore's Theorem

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $G = \struct {V, E}$ be a simple graph of order $n \ge 3$.

Let $G$ be an Ore graph, that is:

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


Then $G$ is Hamiltonian.


Proof

From Ore Graph is Connected it is not necessary to demonstrate that $G$ is connected.

Aiming for a contradiction, 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 $\tuple {v_1, v_2, \ldots, v_{i - 1}, v_n, v_{n - 1}, \ldots, v_i, v_1}$ 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


Source of Name

This entry was named for Øystein Ore.


Historical Note

It was demonstrated by Øystein Ore in $1960$.