<p><strong>EDIT: This proof is wrong, as pointed out in the comments. (Should I delete the post?)</strong></p>

<p>It intuitively feels like if Hamiltonicity is NP-hard for k-regular graphs, then it should also be NP-hard for (k+1)-regular graphs. Here's a back-of-the-envelope reduction, which looks fine to me, but of course there could be a mistake.</p>

<p>Let G be a k-regular graph. Let G' be a the graph Cartesian product of G and an edge. In other words, G' is the graph which has two copies of G, and every vertex is connected to its copy. G' is now (k+1) regular, since each vertex got 1 extra edge.</p>

<p><strong>Claim:</strong> G has a Hamiltonian cycle if and only if G' has a Hamiltonian cycle.</p>

<p><strong>Proof:</strong>  If G has a Hamiltonian cycle, it's easy to see that G' has one too. Say (u,v) is an edge in the Hamiltonian cycle. Traverse the cycle from u to v without using that edge, and now instead of using the edge, go to v' from v, where v' is the vertex corresponding to v in the copy of G. Now traverse the cycle in the reverse order in this graph, which will bring us back to u'. Now go from u' to u, which completes the cycle.</p>

<p>If G' has a Hamiltonian cycle starting from vertex u, consider the same sequence of traversals on G. Every time a move is made to an adjacent vertex in the same graph, we make the same move in G. Every time a move is made to the corresponding vertex in the other graph, we  do nothing. Since every move is valid on the graph G, and the cycle ends on vertex u, this is a Hamiltonian cycle. </p>

CC BY-SA 2.5
2010-09-24T23:10:37.510Z
I cannot see how the second paragraph of the proof works.  If we drop the condition that G is k-regular, letting G be a path gives a counterexample to a claim that if G′ is Hamiltonian then G is also Hamiltonian.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-24T23:11:06.963Z
I'm a bit concerned about the last paragraph here. When the Hamilton cycle for G' is "projected" (if that is the right word!) on to G, we may have a situation where the cycle retraces its steps.
Emil
CC BY-SA 2.5
2010-09-24T23:24:02.570Z
@Tsuyoshi: you have got a counter-example: just take a regular path -  the path with two vertices.
Emil
CC BY-SA 2.5
2010-09-24T23:27:33.220Z
@Tsuyoshi: You're right. The proof is wrong. Should I delete the answer? Do we have a policy on this?
Robin Kothari
CC BY-SA 2.5
2010-09-24T23:52:36.070Z
@Robin, I think your post should be left now that it has generated some discussion. It certainly illustrates that this is an awkward problem.
Emil
CC BY-SA 2.5
2010-09-25T01:34:38.093Z
@Emil: Thanks.  As you can see, I also came to the same counterexample.  I edited my comment many times during the 5-minute window, so excuse me if it confused you.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-24T22:57:50.430Z
2010-09-24T23:26:38.790Z
2010-09-24T23:26:38.790Z
Robin Kothari
<p>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.</p>

<p>The solution is a refinement of the idea suggested in the other answer.</p>

<h2>First part</h2>

<p>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.</p>

<p>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$.</p>

<p>Repeat this for all the vertices of $G$, and let $H$ denote the resulting graph.</p>

<p>Clearly, the graph $H$ is $k+1$ regular. We claim that $H$ is Hamiltonian if and only if $G$ is Hamiltonian. </p>

<p>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.)</p>

<p>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.</p>

<h2>Second part</h2>

<p>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.</p>

<p>We observe, that this implies that the following problem is NP-hard.</p>

<p>Problem A: Deciding if a k-regular graph $G$ with even number of vertices has an Hamiltonian cycle going through a specific edge $e$.</p>

<p>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$:</p>

<ul>
<li>$H$ is $k$-regular.</li>
<li>$H$ is Hamiltonian iff $G$ is Hamiltonian with a cycle using $e$.</li>
<li>$H$ has $|V(G)| + k+1$ vertices => $H$ has odd number of vertices.</li>
</ul>

<hr>

<p>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.</p>

<hr>

<h2>Result</h2>

<p>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.</p>

<hr>

<p>Of course, it is always possible I made some stupid mistake...</p>

<hr>

<h2>Exercise</h2>

<p>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.</p>

<p>(I am posting this as an exercise, not a question, since I know how to solve this.)</p>

CC BY-SA 2.5
2011-01-30T07:38:50.777Z
For the one who is interested for a reference, see [the paper](http://portal.acm.org/citation.cfm?id=182637) by Picouleau in TCS '94.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-09-25T01:57:34.903Z
Great!  I think that this answer in fact settles the first question “For which other k is it known to be NP-complete to test Hamiltonicity of k-regular graphs?” because the 3-regular graphs have an even number of vertices, and the graph H made by this transformation also has an even number of vertices if G has an even number of vertices.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-25T10:37:40.217Z
But unless I'm mistaken, the same counter-example to Robin's proof is a counter-example to this proof. Let G be the path on 2 vertices. Then the procedure here creates H, which is a 9 cycle, which is Hamiltonian.
Emil
CC BY-SA 2.5
2010-09-25T10:40:10.307Z
As I said in regard to Robin's answer, the problem is that when you try to "project" the Hamilton cycle from H on to G, the cycle may end up not being a cycle, because it retraces where it has been.
Emil
CC BY-SA 2.5
2010-09-25T11:52:50.923Z
@Emil: I think that the path on 2 vertices is really a special case because it has a Hamiltonian circuit if we are allowed to use the same edge more than once.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-25T11:56:45.590Z
@Sariel Har-Peled: In every graph, the number of odd vertices (i.e. vertices of odd degree) is even.  Therefore, all the 3-regular graphs have an even number of vertices.  I had written an unnecessarily complicated argument without realizing this in the first version of comment (which I modified in less than 5 minutes), so excuse me if you read my old comment and were confused by it.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-25T12:30:06.643Z
@Tsuyoshi: what do you think about my objection in my second comment?
Emil
CC BY-SA 2.5
2010-09-25T12:34:03.843Z
@Tsuyoshi: I don't really think the path on two vertices is special. It is a graph with a Hamiltonian path, but not a Hamiltonian cycle. If G has a Hamiltonian path, then the H in the proof will have a Hamiltonian cycle... But there are many regular graphs with a Hamiltonian Path but no Hamiltonian cycle, for example the Petersen Graph (http://en.wikipedia.org/wiki/Petersen_graph). So the Petersen Graph is another counter-example.
Emil
CC BY-SA 2.5
2010-09-25T13:07:24.780Z
@Emil: How do you construct a Hamiltonian circuit in H from a Hamiltonian _path_ in G?  For example, consider the case where G is the path on four vertices.  Unless I am mistaken, H is Hamiltonian if and only if G is Hamiltonian, assuming that G has at least three vertices (to avoid the definitional issue about whether the path on two vertices is Hamiltonian or not).
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-25T13:18:48.737Z
@Emil: Let 2n be the number of vertices in G, and call the two copies of G in H $G_1$ and $G_2$.  Unless I am mistaken, any Hamiltonian circuit in H must repeat the following process n times.  Starting from a vertex $u_1$ in $G_1$, visit all the vertices of the clique bridging $u_1$ and the corresponding vertex $u_2$ in $G_2$, visit $u_2$, visit a vertex $v_2$ adjacent to $u_2$ in $G_2$, visit all the vertices of the clique bridging $v_2$ and the corresponding vertex $v_1$ in $G_1$, move to a vertex adjacent to $v_1$ in $G_1$.  Note that you cannot skip the clique.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-25T13:46:57.323Z
Oops yes I've made a mis-think here. I'll think about your latest comment.
Emil
CC BY-SA 2.5
2010-09-25T17:29:16.867Z
I think the proof is correct now! Apart from the path on two vertices. :)
Emil
CC BY-SA 2.5
2010-09-25T19:37:40.710Z
@Ito: You are completely right about the all $3$-regular graphs have even number of vertices. Thanks...
Sariel Har-Peled
CC BY-SA 2.5
2010-09-25T00:10:17.657Z
2010-09-26T22:15:41.010Z
2010-09-26T22:15:41.010Z
Sariel Har-Peled
<p>It is known that it is NP-complete to test whether a Hamiltonian cycle exists in a 3-regular graph, even if it is planar (Garey, Johnson, and Tarjan, SIAM J. Comput. 1976) or bipartite (Akiyama, Nishizeki, and Saito, J. Inform. Proc. 1980) or to test whether a Hamiltonian cycle exists in a 4-regular graph, even when it is the graph formed by an arrangement of Jordan curves (Iwamoto and Toussaint, IPL 1994).</p>

<p>For which other k is it known to be NP-complete to test Hamiltonicity of k-regular graphs?</p>

<p>The particular case I am interested in is 6-regular graphs, with the additional condition that the graph have an odd number of vertices. If this case could be shown to be NP-complete (or polynomial) it would have impact in a graph drawing problem described in <a href="http://arxiv.org/abs/1009.0579">http://arxiv.org/abs/1009.0579</a> . The "odd number of vertices" condition is because what I really want to know is, for 6-regular graphs, whether the graph contains either a Hamiltonian cycle or a bipartite 2-factor; but having an odd number of vertices eliminates the possibility of a bipartite 2-factor leaving only the possibility of a Hamiltonian cycle.</p>

CC BY-SA 4.0
2024-06-04T20:32:23.857Z
Are there similar known results for directed regular graphs?
Avi Tal
<graph-theory><np-hardness><hamiltonian-paths>
Hamiltonicity of k-regular graphs
David Eppstein
# Hamiltonicity of k-regular graphs

(Asked by: username_0 on 2010-09-24)

It is known that it is NP-complete to test whether a Hamiltonian cycle exists in a 3-regular graph, even if it is planar (Garey, Johnson, and Tarjan, SIAM J. Comput. 1976) or bipartite (Akiyama, Nishizeki, and Saito, J. Inform. Proc. 1980) or to test whether a Hamiltonian cycle exists in a 4-regular graph, even when it is the graph formed by an arrangement of Jordan curves (Iwamoto and Toussaint, IPL 1994).

For which other k is it known to be NP-complete to test Hamiltonicity of k-regular graphs?

The particular case I am interested in is 6-regular graphs, with the additional condition that the graph have an odd number of vertices. If this case could be shown to be NP-complete (or polynomial) it would have impact in a graph drawing problem described in <http://arxiv.org/abs/1009.0579> . The "odd number of vertices" condition is because what I really want to know is, for 6-regular graphs, whether the graph contains either a Hamiltonian cycle or a bipartite 2-factor; but having an odd number of vertices eliminates the possibility of a bipartite 2-factor leaving only the possibility of a Hamiltonian cycle.

**Tags:** graph-theory, np-hardness, hamiltonian-paths

> **Comments:**
> **username_1**: Are there similar known results for directed regular graphs?  

---

## 2 answers

### Answer by username_5 on 2010-09-25. Score: 18 | Accepted answer

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.)

> **Comments:**
> **username_3**: Great!  I think that this answer in fact settles the first question “For which other k is it known to be NP-complete to test Hamiltonicity of k-regular graphs?” because the 3-regular graphs have an even number of vertices, and the graph H made by this transformation also has an even number of vertices if G has an even number of vertices.  
> **username_4**: But unless I'm mistaken, the same counter-example to Robin's proof is a counter-example to this proof. Let G be the path on 2 vertices. Then the procedure here creates H, which is a 9 cycle, which is Hamiltonian.  
> **username_4**: As I said in regard to Robin's answer, the problem is that when you try to "project" the Hamilton cycle from H on to G, the cycle may end up not being a cycle, because it retraces where it has been.  
> **username_3**: @username_4: I think that the path on 2 vertices is really a special case because it has a Hamiltonian circuit if we are allowed to use the same edge more than once.  
> **username_3**: @username_5: In every graph, the number of odd vertices (i.e. vertices of odd degree) is even.  Therefore, all the 3-regular graphs have an even number of vertices.  I had written an unnecessarily complicated argument without realizing this in the first version of comment (which I modified in less than 5 minutes), so excuse me if you read my old comment and were confused by it.  
> **username_4**: @Tsuyoshi: what do you think about my objection in my second comment?  
> **username_4**: @Tsuyoshi: I don't really think the path on two vertices is special. It is a graph with a Hamiltonian path, but not a Hamiltonian cycle. If G has a Hamiltonian path, then the H in the proof will have a Hamiltonian cycle... But there are many regular graphs with a Hamiltonian Path but no Hamiltonian cycle, for example the Petersen Graph (http://en.wikipedia.org/wiki/Petersen_graph). So the Petersen Graph is another counter-example.  
> **username_3**: @username_4: How do you construct a Hamiltonian circuit in H from a Hamiltonian _path_ in G?  For example, consider the case where G is the path on four vertices.  Unless I am mistaken, H is Hamiltonian if and only if G is Hamiltonian, assuming that G has at least three vertices (to avoid the definitional issue about whether the path on two vertices is Hamiltonian or not).  
> **username_3**: @username_4: Let 2n be the number of vertices in G, and call the two copies of G in H $G_1$ and $G_2$.  Unless I am mistaken, any Hamiltonian circuit in H must repeat the following process n times.  Starting from a vertex $u_1$ in $G_1$, visit all the vertices of the clique bridging $u_1$ and the corresponding vertex $u_2$ in $G_2$, visit $u_2$, visit a vertex $v_2$ adjacent to $u_2$ in $G_2$, visit all the vertices of the clique bridging $v_2$ and the corresponding vertex $v_1$ in $G_1$, move to a vertex adjacent to $v_1$ in $G_1$.  Note that you cannot skip the clique.  
> **username_4**: Oops yes I've made a mis-think here. I'll think about your latest comment.  
> **username_4**: I think the proof is correct now! Apart from the path on two vertices. :)  
> **username_5**: @Ito: You are completely right about the all $3$-regular graphs have even number of vertices. Thanks...  
> **username_6**: For the one who is interested for a reference, see [the paper](http://portal.acm.org/citation.cfm?id=182637) by Picouleau in TCS '94.  

---

### Answer by username_2 on 2010-09-24. Score: 1

**EDIT: This proof is wrong, as pointed out in the comments. (Should I delete the post?)**

It intuitively feels like if Hamiltonicity is NP-hard for k-regular graphs, then it should also be NP-hard for (k+1)-regular graphs. Here's a back-of-the-envelope reduction, which looks fine to me, but of course there could be a mistake.

Let G be a k-regular graph. Let G' be a the graph Cartesian product of G and an edge. In other words, G' is the graph which has two copies of G, and every vertex is connected to its copy. G' is now (k+1) regular, since each vertex got 1 extra edge.

**Claim:** G has a Hamiltonian cycle if and only if G' has a Hamiltonian cycle.

**Proof:** If G has a Hamiltonian cycle, it's easy to see that G' has one too. Say (u,v) is an edge in the Hamiltonian cycle. Traverse the cycle from u to v without using that edge, and now instead of using the edge, go to v' from v, where v' is the vertex corresponding to v in the copy of G. Now traverse the cycle in the reverse order in this graph, which will bring us back to u'. Now go from u' to u, which completes the cycle.

If G' has a Hamiltonian cycle starting from vertex u, consider the same sequence of traversals on G. Every time a move is made to an adjacent vertex in the same graph, we make the same move in G. Every time a move is made to the corresponding vertex in the other graph, we do nothing. Since every move is valid on the graph G, and the cycle ends on vertex u, this is a Hamiltonian cycle.

> **Comments:**
> **username_3**: I cannot see how the second paragraph of the proof works.  If we drop the condition that G is k-regular, letting G be a path gives a counterexample to a claim that if G′ is Hamiltonian then G is also Hamiltonian.  
> **username_4**: I'm a bit concerned about the last paragraph here. When the Hamilton cycle for G' is "projected" (if that is the right word!) on to G, we may have a situation where the cycle retraces its steps.  
> **username_4**: @Tsuyoshi: you have got a counter-example: just take a regular path -  the path with two vertices.  
> **username_2**: @Tsuyoshi: You're right. The proof is wrong. Should I delete the answer? Do we have a policy on this?  
> **username_4**: @Robin, I think your post should be left now that it has generated some discussion. It certainly illustrates that this is an awkward problem.  
> **username_3**: @username_4: Thanks.  As you can see, I also came to the same counterexample.  I edited my comment many times during the 5-minute window, so excuse me if it confused you.  

---

