Intuition for Ore’s theorem

Question

Ore's theorem states that a graph $G$ is Hamiltonian if every disconnected pair of vertices $u, v \in G$ satisfy $\deg(u) + \deg(v) \geq |G|$.

Is there an easy intuition for remembering this is true? I'm not looking for a formal proof, just the intuition.

Answer 1

Honestly, the best intuition for the condition comes from a good understanding of the proof. The Bondy–Chvátal theorem, which generalizes Ore's theorem, distills the argument down to just the basics: if you have a Hamiltonian path beginning at $u$ and ending at $v$, and the degrees of $u$, $v$ are sufficiently large, then you also have a Hamiltonian cycle. I am not going to restate the whole proof here, but it is a pigeonhole argument on the $n-1$ edges of the Hamiltonian path, hence it takes $\deg(u) + \deg(v) \ge n$ to work.

To remember what the condition has to be (if you remember what it is roughly, but don't quite recall the lower bound it wants), you can also think back to the extreme cases that prove Ore's inequality is tight. These are generally useful to remember. There are two important extreme cases:

1. Two cliques, one with $k+1$ vertices and one with $n-k$ vertices, overlapping at a single vertex (so we have $n$ vertices total). There is no Hamiltonian cycle because the vertex where the cliques meet is a bottleneck. Here, if $u$ and $v$ are not adjacent, then they come from different cliques: $\deg(u)=(k+1)-1$ and $\deg(v)=(n-k)-1$, or vice versa. We get $\deg(u)+\deg(v)=n-1$, so Ore's theorem has to ask for more than this.
2. When $n$ is odd, an unbalanced complete bipartite graph, with $\frac{n-1}{2}$ vertices on one side and $\frac{n+1}{2}$ vertices on the other. There is no Hamiltonian cycle because in a bipartite graph, there is no cycle of odd length. Here, if $u$ and $v$ are not adjacent, then they are on the same side of the bipartition. If they are both on the larger side, then $\deg(u) + \deg(v) = \frac{n-1}{2} + \frac{n-1}{2} = n-1$, so Ore's theorem has to ask for more than this.