# Why HC-k-regular-(n-even) being NP-Complete implies HC-k-regular is NP complete?

In [1], Corollary 2.3, after proving that HC-k-(n-even) for a fixed k >= 3, the paper says that HC-k-regular being NP Complete is an inmediate consequence of the former.

Where: HC-k-regular-(n-even) means if the graph has a hamiltonian cycle in a k-regular graph with an even number of nodes.

And HC-k-regular means the graph has a hamiltonian cycle in a k-regular graph.

I don't understand how or why "HC-k-regular-(n-even) is NP Complete" implies "HC-k-regular is NP Complete". Why graphs with odd number of nodes are not considered in an explicit way?

• inmediate -> immediate? Commented Sep 15, 2022 at 8:17

Hmmm, I think by definition "HC-k-regular-(n-even) is NP-Complete" implies "HC-k-regular is NP-hard", since every NP problem can be reduce to an instance of HC-k-regular-(n-even) problem, which is also a HC-k-regular instance. Together with the obvious result that "HC-k-regular is NP", we can get the conclusion "HC-k-regular is NP-Complete". More intuitively, it's something like "$${\sf SAT} \cup 0^n$$ is NP-Complete".