How to construct a hamilton-connected cubic graph? Is it possible?

Question

If we are given a large integer $k$, can we construct a hamiltonian-connected $n$-vertex graph for every even $n\geq k$ such that all its vertices are of degree 3? Is there any reference concerning this problem? Thanks in advance.

Answer 1

Take a cycle of $2m$ elements, label the vertices around the cycle from $0$ to $2m-1$, and add diagonals $1 \to (2m-1)$, $2 \to (2m-2)$, $\cdots$, $(m-1) \to (m+1)$, and special case $0 \to m$.

By symmetry it suffices to consider the following cases:

1. There is a Hamiltonian path from $0$ to $m$. Take for example $0 \to$ $1 \to$ $(2m-1) \to$ $(2m-2) \to$ $2 \to$ $3 \to$ $(2m-3) \to$ $\cdots \to$ $(m \pm 1) \to$ $(m \mp 1) \to m$ where we alternate "cycle" edges and "diagonal" edges.
2. There is a Hamiltonian path from $0$ to $i$ where $0 < i < m$. We start either $0 \to 1$ or $0 \to 2m-1$ and then alternate "cycle" edges and "diagonal" edges. One of the two initial moves would cause the alternative to include the edge $i \to (2m-i)$, and the other would cause it to include the edge $(2m-i) \to i$. We choose the latter, and break the pattern at $(2m-i)$. We now follow the cycle all the way round to $i$.
3. There is a Hamiltonian path from $i$ to $j$ where $0 < i < j < m$. From $i$ we apply a similar process backwards: $i \to $ $(2m-i) \to$ $(2m-i+1) \to$ $(i-1) \to$ $\cdots 0$. From $j$ we work backwards unlong the cycle $j \leftarrow$ $(j-1) \leftarrow$ $\cdots \leftarrow (i+1)$. Then we take the diagonal $\leftarrow (2m-i-1)$ and again follow the cycle $\leftarrow (2m-i-2)$ $\leftarrow \cdots (2m-j-1)$. Now we alternate diagonals and cycle $\leftarrow (j+1)$ $\leftarrow (j+2)$ $\leftarrow (2m-j-2)$ $\leftarrow \cdots$ $\leftarrow (m \pm 1)$ $\leftarrow m$. Finally we link the two sections with $0 \to m$.
4. There is a Hamiltonian path from $i$ to $j$ where $0 < i < m < j$. A similar strategy applies: if we orient the graph so that $0$ is at the left, $m$ is at the right, and $i$ is in the upper half, then we take case 3 and flip the right-hand side of the graph about a horizontal axis.

There is one special subcase of case 4, where the two endpoints are joined by a diagonal, but in that case we just take one step along the cycle in different directions and start alternating on both sides.