# NP-Hardness of Hamiltonian cycle with $|V|$ divisible by 3

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $|V|$ divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Are DHAM3 and SHAM3 $\mathcal{NP}$-hard?

What I tried is I proved that the problem of finding Hamiltonian cycle is in $\mathcal{NP}$ and that 3-SAT problem, which is $\mathcal{NP}$-Complete, is reducible to Hamiltonian cycle problem which makes it $\mathcal{NP}$-hard, but I am not sure what's the purpose of $|V|$ divisible by 3, does that change anything?

• You might want to try reducing Hamiltonian cycle (which is NP complete) to SHAM3 and DHAM3. This would prove that those problems are NP-hard. Jan 9 '17 at 8:59
• @adrianN yes, but what I am curious about is whether |V| being divisible by 3 is of any use. Jan 9 '17 at 9:08
• The use is making you think of a good reduction from general graphs to graphs with |V| being a multiple of three, I think. Jan 9 '17 at 10:45
• cs.stackexchange.com/q/68410/755
– D.W.
Jan 9 '17 at 17:49

How do you show that DHAM3 is NP-hard by reduction from DHAM? You have to come up with an efficiently computable function $f$ that takes an instance $x$ of DHAM and outputs an instance $f(x)$ of DHAM3 in such a way that $x \in DHAM$ iff $f(x) \in DHAM3$. In other words, $f$ takes a graph $G$ and outputs a graph $f(G)$ whose number of vertices is divisible by 3, and moreover $G$ is Hamiltonian iff $f(G)$ is Hamiltonian.
The difficulty here is that the original graph $G$ might have a number of vertices which is not divisible by 3 (otherwise you can take $f(G) = G$). I'll let you figure out how to overcome this difficulty.