# Limited constant degree HamCycle

Let $$G=(V,E)$$ be a directed graph. I am interested in a "relaxed" version of the HamCycle problem.

In my first case, the degree of each vertex is exactly 6, such that: 3 are outgoing edges and 3 are ingoing edges, for every vertex in $$V$$.

I would like to check whether a HamCycle exists in such a graph. I believe it is still NP-Hard, yet not exactly sure on the details. My initial hunch was to perform a reduction from $$3SAT$$, sort of similar to $$HamCycle$$, but not exactly sure, since the degree is $$6$$, each $$3$$ ingoing and $$3$$ outgoing, so maybe $$3SAT$$ wouldn't work.

The second case was when the indegree and outdegree are exactly $$2$$, but I think it will be clearer after the first case.

Indeed, the standard reduction almost has this property. For each variable, we have a gadget with $$3m+3$$ nodes, where $$m$$ counts the number of clauses in the 3CNF formula $$\varphi$$. Each of those nodes has in-degree 2 and out-degree 2. Then for each clause, we have a node $$c$$, which has in-degree 1 and out-degree 1, and has a connection from the $$i$$th node in each gadget and to the $$i+1$$th node in each gadget. So the only problem are the nodes for the clauses.
We can tweak this to introduce two nodes $$c',c''$$ for each clause. We have a connection from the $$i$$th node in each gadget to both $$c',c''$$; from $$c',c''$$ to the $$i+1$$th node; and edges $$c\to c'$$, $$c'\to c$$. This ensures that each $$c,c'$$ have in-degree 2 and out-degree 2. Moreover, you can verify that the reduction still works.
Related: Hamiltonian cycle is known to be NP-complete even for $$k$$-regular graphs, for all $$k\ge 3$$. See https://cstheory.stackexchange.com/q/1651/5038.