Let SHAM_, be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with V divisible by 3 and DHAM' be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

The Hamiltonian cycle problem (HAM) is a classic NP-complete problem. Both the decision version (DHAM': does a Hamiltonian cycle exist?) and the search version (SHAM: find a Hamiltonian cycle) are NP-hard. For NP-complete problems, the decision and search versions are typically equivalent in complexity - if you can decide existence, you can usually construct the solution through binary search or other methods. Therefore, both DHAM' and SHAM are NP-hard.