How to prove the $NP$-completeness of the language $L$ = $\{$$(G, k)$: the vertices of an undirected graph $G$ can be partitioned into $k$ pairwise disjoint sets of pairwise different sizes so, that all the corresponding induced subgraphs have a Hamiltonian cycle}. I had no problems how to prove that this language is in the $NP$, but it is not clear to me how to prove that this language is in the $NP-hard$ class.
1 Answer
$\begingroup$
$\endgroup$
You can map any $\text{HamiltonianCycle}$ instance $G$ to an $L$-instance $(G, 1)$, yielding a polynomial time reduction from an $\mathsf{NP}$-complete problem to $L$ which implies the $\mathsf{NP}$-hardness of $L$.
