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?

SHAM₃ (finding Hamiltonian cycle in graphs where |V| is divisible by 3) is at least as hard as DHAM₃ (deciding existence). Since finding a solution is always at least as hard as deciding existence (given a finding algorithm, we can decide existence), SHAM₃ is NP-hard if DHAM₃ is. DHAM₃ is a special case of the Hamiltonian cycle problem, which is NP-complete, so DHAM₃ is NP-hard. Therefore both are NP-hard.