Lesson 5

Theorem (Ore, 1960).

1. If for any two non-adjacent vertices \(u\) and \(v\) of an undirected graph the condition \(\deg(u)+\deg(v) \ge n-1\) holds, then the graph has a Hamiltonian path.
2. If for any two non-adjacent vertices \(u\) and \(v\) of an undirected graph the condition \(\deg(u)+\deg(v) \ge n\) holds, then the graph has a Hamiltonian cycle.

Proof.

1. If \(n=2\), then everything is obvious. Now let \(n>2\). Note that the graph is connected: if there is no edge between two vertices, then the condition on their degrees guarantees that they have a common neighbor (and, therefore, a path of length two). Let \(v_{1} \to v_{2} \to \dotsb \to v_{k}\) be the longest (simple) path in \(G\). If \(k=n\), then there is nothing to prove, so assume that \(k<n\) (and arrive at a contradiction). If \(\{v_{1},v_{k}\} \in E\), then there is also a cycle of length \(k\), and if \(\{v_{1},v_{k}\} \not \in E\), then the existence of such a cycle is guaranteed by the lemma (since \(\deg(v_{1})+\deg(v_{k}) \ge n-1 \ge k\)). This \(k\)-cycle must be connected to the remaining part of the graph, but then there is also a path of length \(k+1\).
2. A Hamiltonian path \(v_{1} \to \dotsb \to v_{n}\) exists by point \(1\). If \(\{v_{1}, v_{n}\} \in E\), then there is also a Hamiltonian cycle. If \(\{v_{1}, v_{n}\} \not \in E\), then a Hamiltonian cycle exists by the lemma.