# Is Hamiltonian cycle problem on graphs with out-degree at most 3 NP hard?

I am trying to show a different form of Hamiltonian cycle problem is NP Hard. The problem is as follows.

We have a directed graph and each node can have at most 3 outgoing edges. Determine if this graph has a Hamiltonian cycle.

Is this problem NP hard?

I just need to find a problem to reduce to my problem but could achieve to find none.

3SAT looks friendly to me as it has 3-termed clauses but no more I progressed.

• Try reduction from the usual Hamiltonian cycle problem. – Yuval Filmus Mar 28 at 13:26
• @YuvalFilmus yeah but I do not want answer but just a hint to go on – Davis Mar 28 at 14:59
• I already gave you a hint. Try a reduction from Hamiltonian cycle. I don't know if the hint works, but it seems like a good thing to try. – Yuval Filmus Mar 28 at 15:01
• Hint: When reducing from Hamiltonian Cycle as suggested by @YuvalFilmus, you can add many more "helping" vertices to each original vertex, provided you can figure out a way to let them all be visited when the original vertex is. – j_random_hacker Mar 28 at 15:02
• If you has figured out this problem, please write an answer (yes, you can answer your own question). – xskxzr Mar 29 at 17:37