[proofplan] We first establish connectivity: if $x \not\sim y$, the neighbourhood sizes $|N(x)|, |N(y)| \geq n/2$ force $N(x) \cap N(y) \neq \varnothing$ by pigeonhole, giving a 2-edge path between $x$ and $y$. Next, take a path $x_1, \ldots, x_\ell$ of maximum length in $G$; maximality forces all neighbours of $x_1$ and $x_\ell$ to lie on the path itself. Define $N^-(x_1) = \{x_i : x_{i+1} \in N(x_1)\}$; by a pigeonhole count inside $\{x_1, \ldots, x_{\ell-1}\}$, $N^-(x_1) \cap N(x_\ell) \neq \varnothing$, yielding a cycle of length $\ell$ via path reversal. Finally, if $\ell < n$, connectivity provides a vertex adjacent to the cycle, which extends the path beyond length $\ell$, contradicting maximality. Hence $\ell = n$ and the cycle is a Hamilton cycle. [/proofplan] [step:Show $G$ is connected by pigeonhole on neighbourhoods of non-adjacent vertices] Suppose $x, y \in V(G)$ are distinct. If $x \sim y$ they are already connected by an edge. Otherwise $x \neq y$ and $x \not\sim y$. Both $N(x) \subseteq V(G) \setminus \{x\}$ and $N(y) \subseteq V(G) \setminus \{y\}$, and since $x \not\sim y$, $x \notin N(y)$ and $y \notin N(x)$. Hence $N(x), N(y) \subseteq V(G) \setminus \{x, y\}$, a set of size $n - 2$. We have $|N(x)| = \deg(x) \geq \delta(G) \geq n/2$ and similarly $|N(y)| \geq n/2$. By inclusion-exclusion, \begin{align*} |N(x) \cap N(y)| = |N(x)| + |N(y)| - |N(x) \cup N(y)| \geq \frac{n}{2} + \frac{n}{2} - (n - 2) = 2. \end{align*} In particular $N(x) \cap N(y) \neq \varnothing$: there exists $z \in N(x) \cap N(y)$, giving the path $x, z, y$ of length $2$. Hence $x$ and $y$ lie in the same connected component of $G$. Since this holds for every pair $x, y \in V(G)$, $G$ is connected. [guided] The connectivity step is prerequisite to later steps (the path-extension argument at the end requires $G$ connected, since "$G - V(P)$ is non-empty" combined with "some vertex of $G - V(P)$ is adjacent to some vertex of $P$" requires connectedness of $G$). **Pigeonhole logic.** $N(x)$ and $N(y)$ are both subsets of the $(n-2)$-element set $V(G) \setminus \{x, y\}$. Each has size at least $n/2$. Two subsets of a set of size $n - 2$, each of size at least $n/2$, must overlap: their total size is at least $n > n - 2$, so they cannot fit disjointly. More precisely, $|N(x) \cap N(y)| \geq n/2 + n/2 - (n - 2) = 2$. **Why did we need $\delta(G) \geq n/2$?** If we only had $\delta(G) \geq n/2 - 1$, the pigeonhole bound would give $|N(x) \cap N(y)| \geq 0$, which is useless. The exact hypothesis $\delta(G) \geq n/2$ is what forces non-empty intersection and hence connectivity. **Does this argument use $n \geq 3$?** Yes, indirectly: for $n = 2$, $\delta(G) \geq 1$ means every vertex has a neighbour, which in a two-vertex graph means $x \sim y$, so there is nothing to prove. For $n = 1$ the theorem statement is vacuous ($n \geq 3$). The hypothesis $n \geq 3$ is essential later for the cycle construction. [/guided] [/step] [step:Take a maximum-length path and observe neighbours of its endpoints lie on the path] Let $P: x_1, x_2, \ldots, x_\ell$ be a path in $G$ of **maximum length** (i.e., maximum number of vertices). Such a path exists because $G$ is finite. **Claim:** $N(x_1) \subseteq \{x_2, x_3, \ldots, x_\ell\}$, and similarly $N(x_\ell) \subseteq \{x_1, x_2, \ldots, x_{\ell-1}\}$. *Proof of claim.* If $x_1$ had a neighbour $w \notin V(P) = \{x_1, \ldots, x_\ell\}$, then prepending $w$ to $P$ gives the path $w, x_1, x_2, \ldots, x_\ell$ of length $\ell + 1$ (one more vertex than $P$), contradicting maximality. Hence every neighbour of $x_1$ lies in $V(P)$, and since $x_1 \notin N(x_1)$ (no loops), $N(x_1) \subseteq \{x_2, \ldots, x_\ell\}$. The argument for $x_\ell$ is symmetric. In particular, since $\deg(x_1) \geq n/2$ and $\deg(x_\ell) \geq n/2$, we have $\ell - 1 \geq \max(\deg(x_1), \deg(x_\ell)) \geq n/2$, so $\ell \geq n/2 + 1$. [guided] **Why does a maximum-length path exist?** $G$ is finite, so the set of paths in $G$ is finite, and we can pick one with the greatest number of vertices. **Why does $N(x_1) \subseteq V(P)$?** This is the standard **extremal argument**: if $x_1$ had a neighbour outside $V(P)$, we could extend $P$ by adding that neighbour, contradicting maximality. Maximum-length-path arguments always exploit this: endpoints of the extremal path have no neighbours outside the path. **Why the lower bound $\ell \geq n/2 + 1$?** Since $|N(x_1)| \geq n/2$ and $N(x_1) \subseteq \{x_2, \ldots, x_\ell\}$, the latter set has at least $n/2$ elements. It has exactly $\ell - 1$ elements, so $\ell - 1 \geq n/2$, i.e., $\ell \geq n/2 + 1 \geq 2$. (For $n = 3$: $\ell \geq 2.5$, so $\ell \geq 3$.) The inclusion of $x_1$'s and $x_\ell$'s neighbourhoods in $V(P)$ means we can count them inside $\{x_1, \ldots, x_{\ell-1}\}$, a set of size $\ell - 1 \leq n - 1$. We will apply pigeonhole next. [/guided] [/step] [step:Find a cycle of length $\ell$ by pigeonhole on $N^-(x_1)$ and $N(x_\ell)$] Define \begin{align*} N^-(x_1) := \{x_i \in V(P) : 1 \leq i \leq \ell - 1,\ x_{i+1} \in N(x_1)\}. \end{align*} The map $x_i \mapsto x_{i+1}$ is a bijection from $N^-(x_1) \subseteq \{x_1, \ldots, x_{\ell-1}\}$ to $N(x_1) \cap \{x_2, \ldots, x_\ell\} = N(x_1)$ (the latter equality by the endpoint claim). Hence \begin{align*} |N^-(x_1)| = |N(x_1)| \geq \frac{n}{2}. \end{align*} Similarly $|N(x_\ell)| \geq n/2$, and $N(x_\ell) \subseteq \{x_1, \ldots, x_{\ell-1}\}$. Both $N^-(x_1)$ and $N(x_\ell)$ are subsets of $\{x_1, \ldots, x_{\ell-1}\}$. But $x_1 \notin N^-(x_1)$ (since $x_0$ does not exist — or more precisely, the defining condition $x_0 \in N(x_1)$ is vacuous as $x_0$ is not a vertex; formally, $N^-(x_1) \subseteq \{x_1, \ldots, x_{\ell-1}\}$ is all we need for the counting). By pigeonhole, \begin{align*} |N^-(x_1) \cap N(x_\ell)| \geq |N^-(x_1)| + |N(x_\ell)| - (\ell - 1) \geq \frac{n}{2} + \frac{n}{2} - (\ell - 1) = n - \ell + 1. \end{align*} Since $\ell \leq n$ (the path has at most $n$ vertices), we have $n - \ell + 1 \geq 1$, so $N^-(x_1) \cap N(x_\ell) \neq \varnothing$. Pick any $x_i \in N^-(x_1) \cap N(x_\ell)$. Then $x_{i+1} \in N(x_1)$ and $x_i \in N(x_\ell)$. Construct the cycle \begin{align*} C: x_i, x_\ell, x_{\ell-1}, \ldots, x_{i+2}, x_{i+1}, x_1, x_2, \ldots, x_{i-1}, x_i. \end{align*} Explicitly: $C$ traverses $x_i \to x_\ell$ (edge), then the path $P$ in reverse from $x_\ell$ to $x_{i+1}$ (edges $x_\ell x_{\ell-1}, \ldots, x_{i+2} x_{i+1}$), then $x_{i+1} \to x_1$ (edge), then the path $P$ forward from $x_1$ to $x_i$ (edges $x_1 x_2, \ldots, x_{i-1} x_i$). The cycle $C$ has exactly $\ell$ vertices (all vertices of $P$) and $\ell$ edges, hence is a cycle of length $\ell$. [illustration:ore-dirac-cycle-construction] [guided] **Why the definition $N^-(x_1) = \{x_i : x_{i+1} \in N(x_1)\}$?** We want to convert "neighbours of $x_1$" on the path (which are $\{x_{i+1} : x_{i+1} \in N(x_1)\}$) into their **predecessors** on the path. This is because the rotation trick below needs two pieces of data at position $i$: that $x_i$ is adjacent to $x_\ell$ (the rotation point for the cycle-closure edge), and that $x_{i+1}$ is adjacent to $x_1$ (the other cycle-closure edge). Both pieces are shifted forms of standard neighbourhoods. **Pigeonhole count.** $N^-(x_1)$ and $N(x_\ell)$ are both subsets of $\{x_1, \ldots, x_{\ell-1}\}$ (size $\ell - 1$). Each has size at least $n/2$. The pigeonhole bound gives \begin{align*} |N^-(x_1) \cap N(x_\ell)| \geq n/2 + n/2 - (\ell - 1) = n - \ell + 1 \geq 1 \end{align*} since $\ell \leq n$. **The rotation trick — why is $C$ a cycle?** We take the maximum path $P = x_1 x_2 \cdots x_\ell$ and modify it. We know $x_{i+1} \in N(x_1)$ and $x_i \in N(x_\ell)$. Build the cycle by: 1. Starting at $x_i$, go to $x_\ell$ (the new edge $x_i x_\ell$). 2. Traverse $P$ backward from $x_\ell$ to $x_{i+1}$: this uses edges $x_\ell x_{\ell-1}, x_{\ell-1} x_{\ell-2}, \ldots, x_{i+2} x_{i+1}$. 3. From $x_{i+1}$, go to $x_1$ (the new edge $x_{i+1} x_1$). 4. Traverse $P$ forward from $x_1$ to $x_i$: uses edges $x_1 x_2, x_2 x_3, \ldots, x_{i-1} x_i$. All vertices $x_1, \ldots, x_\ell$ appear exactly once on this closed walk, each edge is traversed exactly once, so $C$ is a cycle of length $\ell$ (with $\ell$ vertices and $\ell$ edges). **Edge count sanity check.** The original path had $\ell - 1$ edges. We dropped the edges $x_i x_{i+1}$ (to "break open" the path) — no, wait, we didn't drop it: we traversed $P$ from $x_1$ to $x_i$ and $P$ from $x_\ell$ back to $x_{i+1}$, so we used all edges of $P$ except the single edge $x_i x_{i+1}$. Then we added the two new edges $x_i x_\ell$ and $x_1 x_{i+1}$. Net edge count: $(\ell - 1) - 1 + 2 = \ell$. Cycle of length $\ell$. [/guided] [/step] [step:Show the cycle must span all vertices, using connectivity to rule out $\ell < n$] We have constructed a cycle $C$ of length $\ell$ in $G$, using every vertex of the path $P$. Suppose for contradiction that $\ell < n$. Then $V(G) \setminus V(C) \neq \varnothing$: pick $w \in V(G) \setminus V(C)$. Since $G$ is connected (from the first step) and $V(C)$ is non-empty, there is a path in $G$ from $w$ to some vertex of $C$. Consider a shortest such path; its first edge goes from $w$ to some neighbour $w'$ of $w$. If $w' \in V(C)$, then $w' = x_j$ for some $j$. In that case, we construct a path of length $\ell + 1$ as follows: \begin{align*} w, x_j, x_{j+1}, \ldots, x_{j-1} \pmod{\ell} \end{align*} traversing the cycle $C$ starting from $x_j$ and going all the way around (along $\ell - 1$ cycle edges to return to $x_{j-1}$), using $w$ as a prepended vertex. This is a path with $\ell + 1$ vertices and $\ell$ edges — one more vertex than $P$. More generally, if $w$ is not directly adjacent to $C$, follow the shortest-path from $w$ towards $C$ one step at a time; at some point an adjacency with $C$ is achieved, and the construction above applies to that first $C$-adjacent vertex. In all cases we obtain a path with more than $\ell$ vertices, contradicting the maximality of $P$. Hence $\ell = n$, and $C$ is a cycle on all $n$ vertices of $G$: a Hamilton cycle. [guided] The final step is a classical path-extension argument. We have a cycle $C$ of length $\ell$ and, if $\ell < n$, some vertex outside $C$. Connectivity says there is a path from the outside to the cycle. The first cycle-neighbour along such a path lets us build a longer path: - Start at $w$ (outside the cycle). - Step into the cycle at $x_j$. - Traverse the entire cycle from $x_j$, going around through $x_{j+1}, x_{j+2}, \ldots, x_{j-1}$ (indices mod $\ell$), using every cycle vertex exactly once. This produces a path $w, x_j, x_{j+1}, \ldots, x_{j-1}$ with $\ell + 1$ vertices, which has $\ell$ edges. It is longer than $P$, which had only $\ell - 1$ edges and $\ell$ vertices — contradiction with maximality of $P$. **Key insight:** **a long cycle plus a single adjacent outside vertex gives an even longer path.** This is the classical "a cycle is worse than a path" observation: if $G$ is connected and has a long cycle not covering everything, you can unfold a cycle into a path that also includes an extra vertex, gaining one. **Why was connectivity essential?** Without connectivity, the outside vertex $w$ might be in a different component than $C$, and no edge would connect the two — no path extension possible. The first step of the proof (establishing connectivity via pigeonhole) is precisely what makes this argument work. **Conclusion.** $\ell = n$ and $C$ is a cycle of length $n$ using every vertex of $G$ — a Hamilton cycle. Since $G$ has a Hamilton cycle, $G$ is Hamiltonian. [/guided] [/step]