# How to reduce the hamiltonian path problem to 1/2 hamiltonian path problem

Show that: $$HPP \le_{P} 1/2-HPP$$
Question: Can anyone give me a hint on how to prove $$HPP \le_{P} 1/2-HPP$$
Double the graph size: make two clones of the input $$G_1,G_2$$ and now create the (not connected) graph $$\hat G$$ that will consist of the two clones $$G_1,G_2$$. Now a half-hamiltonian path in $$\hat G$$ is either going through all $$G_1$$ or all $$G_2$$ (but not both, since they are not connected) and thus would be a hamiltonian path in $$G$$.
You just need to add $$n$$ (where $$n$$ is the order of the graph) vertices with no additional edges.