Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V,E)…

Final answer: Both the decision problem of determining whether a Hamiltonian cycle exists in graphs whose number of vertices is divisible by 3 and the search problem of finding such a Hamiltonian cycle are NP-hard.

Key idea: reduce the general Hamiltonian cycle problem to the restricted problem by subdividing an edge the required number of times to make the vertex count divisible by 3.

• Given any input graph G with n vertices, choose an edge (x,y) of G (if G has no edges then G trivially has no Hamiltonian cycle unless n is small; such cases are handled separately).

• If n mod 3 = 0 do nothing. If n mod 3 = 1 add two new vertices by replacing edge (x,y) with the path x — v1 — v2 — y (two subdivisions). If n mod 3 = 2 add one new vertex by replacing (x,y) with x — v1 — y (one subdivision).

• Subdivision preserves Hamiltonicity: the newly added vertices have degree 2, so any Hamiltonian cycle in the modified graph must traverse the path through them; collapsing that path back to the original edge gives a Hamiltonian cycle in the original graph. Conversely, any Hamiltonian cycle in the original graph that used edge (x,y) can be converted into a Hamiltonian cycle in the modified graph by replacing (x,y) with the corresponding path. Thus G has a Hamiltonian cycle iff the modified graph G' does.

• The transformation is polynomial-time and makes |V(G')| divisible by 3, so it is a valid reduction from the general Hamiltonian cycle problem to the restricted decision problem.

• Therefore the decision problem on graphs with vertex count divisible by 3 is NP-hard (indeed NP-complete). The same reduction shows the search version is also at least as hard as the general search problem, so the search problem is NP-hard as well.

Conclusion: Both the decision and search variants restricted to graphs whose number of vertices is divisible by 3 are NP-hard.