Proof of Ore's theorem

Proof

We argue by contradiction, with an edge-maximal counterexample.

1. Let $G$ be a finite simple graph with vertex set $V$ and $n = \abs{V} \ge 3$. Suppose that $\deg(u) + \deg(v) \ge n$ for all distinct nonadjacent $u, v$.
2. Suppose, for a contradiction, that $G$ is not Hamiltonian.
3. Consider the graphs $H$ on the vertex set $V$ that contain every edge of $G$ and are not Hamiltonian. Choose one with the largest number of edges. Such an $H$ exists, because $G$ is one of these graphs and there are finitely many graphs on $V$.
4. Each vertex has at least the same degree in $H$ as in $G$, because $H$ contains all edges of $G$.
5. The graph $H$ is not the complete graph on $V$. Indeed, for $n \ge 3$ the complete graph has the Hamiltonian cycle that visits the vertices in any order.
6. So $H$ has two distinct nonadjacent vertices $u$ and $v$. They are also nonadjacent in $G$, so by Steps 1 and 4, $\deg_H(u) + \deg_H(v) \ge n$.
7. By the choice of $H$ in Step 3, the graph $H + uv$ is Hamiltonian. Its Hamiltonian cycle uses the edge $uv$, since otherwise it would be a Hamiltonian cycle of $H$.
8. Remove the edge $uv$ from this cycle. What remains is a path $w_1, w_2, \dots, w_n$ in $H$ that contains every vertex, with $w_1 = u$ and $w_n = v$.
9. Let $A = \set{i \in \set{1, \dots, n-1} : u w_{i+1} \text{ is an edge of } H}$. The neighbours of $u$ lie among $w_2, \dots, w_n$, so $\abs{A} = \deg_H(u)$.
10. Let $B = \set{i \in \set{1, \dots, n-1} : w_i v \text{ is an edge of } H}$. The neighbours of $v$ lie among $w_1, \dots, w_{n-1}$, so $\abs{B} = \deg_H(v)$.
11. The sets $A$ and $B$ lie in $\set{1, \dots, n-1}$, which has $n - 1$ elements. So $\abs{A \cup B} \le n - 1$. By Step 6, $\abs{A \cap B} = \abs{A} + \abs{B} - \abs{A \cup B} \ge n - (n-1) = 1$. Let $i \in A \cap B$.
12. Since $u$ and $v$ are not adjacent, $1 \notin B$ and $n - 1 \notin A$. Hence $2 \le i \le n-2$.
13. Consider the closed walk $w_1, w_2, \dots, w_i, w_n, w_{n-1}, \dots, w_{i+1}, w_1$. Its edges are path edges, the edge $w_i w_n$ (as $i \in B$) and the edge $w_{i+1} w_1$ (as $i \in A$).
14. This closed walk visits each of the $n \ge 3$ vertices exactly once before it returns to $w_1$. So it is a Hamiltonian cycle of $H$.
15. This contradicts the choice of $H$ as a non-Hamiltonian graph. Hence $G$ is Hamiltonian.