# 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. – adrianN 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. – Rakesh K 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. – adrianN 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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.94091517,"math_prob":0.99609375,"size":1117,"snap":"2020-45-2020-50","text_gpt3_token_len":289,"char_repetition_ratio":0.11051213,"word_repetition_ratio":0.019512195,"special_character_ratio":0.2533572,"punctuation_ratio":0.05652174,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9995227,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-11-23T17:12:41Z\",\"WARC-Record-ID\":\"<urn:uuid:54fe2e8e-339c-49e8-9849-ce182a2a90cd>\",\"Content-Length\":\"156228\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:975e93a4-7697-456a-b39f-0de687ee0a6b>\",\"WARC-Concurrent-To\":\"<urn:uuid:e62c5c51-bdf9-492e-9a71-7ed325f1a86d>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/68448/np-hardness-of-hamiltonian-cycle-with-v-divisible-by-3/68477\",\"WARC-Payload-Digest\":\"sha1:XOIFT4S2H74LXYASZMMGWW57CYQRZOHH\",\"WARC-Block-Digest\":\"sha1:KARMQHSEWDPDVZTAWS7GW7VXR2I663YY\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-50/CC-MAIN-2020-50_segments_1606141163411.0_warc_CC-MAIN-20201123153826-20201123183826-00648.warc.gz\"}"}