Problem Partition-into-Hamiltonian-Subgraphs (PiHS):

Input:

A graph G= (V; E) and a positive integer k<=|V|

Question:

Can the set V of vertices be partitioned into exactly k disjoint sets V1; V2; V3.... Vk such that, for 1<=i<=k, the subgraph induced by subset Vi contains a Hamiltonian cycle?

(a) Give a new yes-instance of Problem PiHS.

(b) Give a new no-instance of Problem PiHS.

(c) Prove that Problem PiHS is in the class NP