There is a theorem of Nash-Williams that an $n$-regular graph on $2n+1$ vertices is Hamiltonian. I found a proof here, but I have difficulty understanding it. In my browser, I just see a bunch of LaTex commands when I look at the page, so I have converted it to MathJax:
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 $d(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.
I understand the proof up to the point where it establishes that $G$ has a Hamilton path. Then the author supposes that $G$ has no Hamilton cycle, and I lose the thread. He says, "It follows that if $ v_0v_i \in E $, then $ v_{i-1}v_{2n}\notin E.$" I see this, for otherwise, we have the Hamilton cycle $$v_0,v_i,v_{i+1},\dots,v_{2n},v_{i-1},v_{i-2},\dots,v_0.$$ But then he says, "and also that if $ v_0v_i \notin E $, then $ v_{i-1}v_{2n}\in E$." I don't follow this at all. Why can it not be the case that $v_0$ and $v_i$ are not adjacent, and neither are $v_{i-1}$ and $v_{2n}$?
There is perhaps an omission here, for later in the proof, he says, "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$." I thought perhaps the condition $v_0v_{i+1}\in E$ had been omitted earlier, but even then, I don't see why this is true. How does the absence of one edge ever dictate the presence of another?
After searching for this (surprisingly rare) proof, I have found another reference here, in which we can find the same claim, but is not much explained either.
I believe I have found the argument :
Let us define $v_{i-1}$ to be a potential neighbour of $v_{2n}$ if $v_0v_i\notin E$. This terminology makes sense as if $v_0v_i\in E$, $v_{i-1}$ is not allowed being a neighour of $v_{2n}$, although we do not know that every potential neighbour is necessarily a neighbour.
As $v_0$ has $n-1$ neighbours in $\{v_2,\dots,v_{2n-1}\}$ (as we removed $v_1$), we can deduce that $(2n-2)-(n-1)=n-1$ vertices of $\{v_1,\dots,v_{2n-2}\}$ are potential neighbours of $v_{2n}$, as we must remove all vertices such that the next is a neighbour of $v_0$.
But we know that $v_{2n}$ has degree $n$, and thus as $v_{2n-1}v_{2n}\in E$, we know that $v_{2n}$ has $n-1$ neighbours in $\{v_1,\dots,v_{2n-2}\}$. Thus, this means that every potential neighbour must be a neighbour.
In other words, if $v_0v_i\notin E$, then $v_{i-1}v_{2n}\in E$, as $v_{i-1}$ is a potential neighbour of $v_{2n}$ and every potential neighbour is a neighbour.