# Nash-Williams theorem on the Hamiltonian property of some regular graphs

I have been digging on the internet for the proof of this theorem for the last couple of days without success. The result was published by Sir Crispin Nash-Williams as Valency Sequences which force graphs to have Hamiltonian Circuits. Interim Rep, University of Waterloo Res Rep., Waterloo, Ontario, 1969. However, this old paper is unavailable online but I have a proof in some lecture notes from my class, that I want to share here.

Theorem. Let $G=(V, E)$ be an $n$-regular graph with $|V| = 2n + 1$. Then, $G$ is Hamiltonian.

Proof. We first remark that $n$ must be even, since $$\sum_{x \in V} d(x) = n(2n + 1) = 2|E|$$ We might try to apply Dirac’s theorem, which would give us a Hamiltonian cycle if $\forall x \in V, d(x) \geq \frac{|V|}{2}$. But in the current case, $\forall x \in V, d(x) = n \< \frac{2n+1}{2}$.

So we force Dirac by adding an extra vertex $w$ and connecting it to all $x \in V$. In this new graph $G’$, $d(x) = n + 1 \forall x \in V$ and $d(w) = 2n + 1$. Therefore we have a Hamiltonian cycle that passes through $w$ and in which, $w$ is adjacent to two vertices $x$ and $y \in V$. Therefore this cycle induces a Hamiltonian path in $G$: $$P = [x = v_0, v_1, …, v_{2n-1}, v_{2n}=y]$$

Suppose that $G$ is not Hamiltonian. It follows that if $v_0v_i \in E$, then $v_{i-1}v_{2n} \notin E$ and also that if $v_0v_i \notin E$, then $v_{i-1}v_{2n} \in E$.

We have two cases. If $v_0$ is adjacent to $v_1, …, v_n$ then it follows that $v_{2n}$ is adjacent to $v_n, v_{n+1}, …, v_{2n-1}$, since it cannot be adjacent to any $v_i, i \< n$ without creating a Hamiltonian cycle. But in this case, in the graph induced by the first half $G[\{v_0, v_1, … v_n\}]$, $v_n$ cannot be adjacent to all the others, since in $G$ it has degree $n$ and it already has $2$ outgoing edges. So there is at least one vertex $v_i, i \< n$ that isn’t adjacent to it, which means $v_i$ is adjacent to some $v_j, j > n$, thus forming a Hamiltonian cycle.

In the second case, we have a vertex $v_i, 2 \leq i \leq 2n - 1$ such that $v_0v_i \notin E$ and $v_0v_{i+1} \in E$. This also means that $v_{i-1}v_{2n} \in E$.

We therefore have a cycle of length $2n$ in $G$ that excludes $v_i$. Let’s rename this cycle $C=[y_1, y_2, …, y_{2n}, y_1]$ and $v_i=y_0$.

$y_0$ cannot be adjacent to two consecutive vertices $y_i$ and $y_{i+1}$ because this will give a Hamiltonian cycle. But we know that $deg(y_0) = n$. It follows that it’s adjacent to all of the even or odd numbered vertices. We assume the latter, without loss of generality. Let $2k$ be some even index. Notice that we have $\{y_0y_{2k-1}, y_0y_{2k+1}\} \subset E$ and we can follow the cycle $C$ from $y_{2k+1}$ all the way back to $y_{2n-1}$ giving us a new cycle $C’ = [y_1, y_2, …, y_{2n-1}, y_0, y_{2k+1}, …, y_{2n}, y_1]$ also of length $2n$. So by repeating the same reasoning for every even vertex, by placing it in the middle and building a cycle around it, it follows that every even vertex is adjacent to all the odd vertices. But there are $n+1$ even indices, so it follows that the degree of any odd vertex is at least $n+1$, contradicting the initial conditions of the theorem. $\square$