First step let assume the graph has even number of vertices. In the second stage, we will extend the construction, so that if k is even, then we will show how to turn the graph into having odd number of vertices.
The solution is a refinement of the idea suggested in the other answer.
First part
Claim: Given a $k$-regular graph $G$ with even number of vertices, one can compute a graph $H$ which is $(k+1)$-regular, and $H$ is Hamiltonian iff $G$ is Hamiltonian.
Proof:
Take two copies of the $k$-regular graph $G$, let call them $G_1$ and $G_2$. For a vertex $v \in V(G)$, let $v_1$ and $v_2$ be the corresponding copies. Create a clique with $k+2$ vertices for $v$. Pick two vertices $v'$ and $v''$ in this clique, and remove the edge between them. Next, connect $v_1$ to $v'$ and $v_2$ to $v''$. Let $C(v)$ denote this component for $v$.
Repeat this for all the vertices of $G$, and let $H$ denote the resulting graph.
Clearly, the graph $H$ is $k+1$ regular. We claim that $H$ is Hamiltonian if and only if $G$ is Hamiltonian.
One direction is clear. Given a Hambiltonian cycle in $G$, we can translate it into a cycle in $H$. Indeed, whenever the cycle visits a vertex $v$, we interpret it as moving from $v_1$ to $v_2$ (or vice versa) while visiting all the vertices in $C(v)$.
As such, this results in a Hamiltonian cycle in $H$. (Note, that this is where we are using the fact that the original number of vertices is even - if the cycle is odd this breaks down.)
As for the other direction, consider a Hamiltonian cycle in $H$. It must be that $C(v)$ is visited by a portion of the cycle that starts in $v_1$, visits all the vertices of $C(v)$ and leaves from $v_2$ (or the symmetric option). Indeed, the Hamiltonian cycle can not enter and leave from the same $v_i$. As such, a Hamiltonian cycle in $H$ as a natural interpretation as a Hamiltonian cycle in $G$.
QED.
Second part
As noted below by Tsuyoshi any 3-regular graph has even number of vertices. As such, the problem is hard for a $3$-regular graph with even number of vertices. Namely, the above reduction shows the problem is hard for any $k$-regular graph, although the resulting graph has an even number of vertices.
We observe, that this implies that the following problem is NP-hard.
Problem A: Deciding if a k-regular graph $G$ with even number of vertices has an Hamiltonian cycle going through a specific edge $e$.
However, if $k$ is even then given an instance $(G, e)$ we can reduce it to desired problem. Indeed, we replace the edge $e$ by a clique of $k+1$ vertices, as before deleting one edge in the clique, and connecting its two endpoints to the endpoints of $e$, and removing $e$ from the graph. Clearly, for the new graph $H$:
- $H$ is $k$-regular.
- $H$ is Hamiltonian iff $G$ is Hamiltonian with a cycle using $e$.
- $H$ has $|V(G)| + k+1$ vertices => $H$ has odd number of vertices.
Note, that a $k$-regular graph, for $k$ odd, must have an even number of vertices (just count the edges), As such, there are no $k$-regular graphs with odd number of vertices, with $k$ being odd.
Result
It is NP-Hard to decide if a $k$-regular graph has a Hamiltonian cycle for $k\geq 3$. The problem remains NP-Hard even if the graph has an odd number of vertices.
Of course, it is always possible I made some stupid mistake...
Exercise
If we want to go from a graph that is $k$-regular to a graph that is (say) $2k$-regular then the graph resulting from applying the above reduction repeatedly results in a graph with a size that depends exponentially on $k$. Show, that given a $k$-regular graph $G$, and $i >2$, one can construct a graph $H$ that is $(k+i)$-regular and its size is polynomial in $k,i$ and $n$, where $n$ is the number of vertices of $G$. Furthermore, $G$ is Hamiltonian if and only if $H$ is Hamiltonian.
(I am posting this as an exercise, not a question, since I know how to solve this.)
