I'm looking for an explanation on how reducing the Hamiltonian cycle problem to the Hamiltonian path's one (to proof that also the latter is NP-complete). I couldn't find any on the web, can someone help me here? (linking a source is also good).
Thank you.
On
For the directed case,
Given $\langle G=(V,E)\rangle$ for the Hamiltonian cycle, we can construct input $\langle G',s,t\rangle$: choose a vertex $u \in V$ and divide it into two vertices, such that the edges that go out of $u$, will go out of $s$ and the vertices that get in to $u$, will get in to $t$.
Note: The below is a Cook reduction and not a Karp reduction. The modern definitions of NP-Completeness use the Karp reduction.
For a reduction from Hamiltonian Cycle to Path.
Given a graph $G$ of which we need to find Hamiltonian Cycle, for a single edge $e = \{u,v\}$ add new vertices $u'$ and $v'$ such that $u'$ is connected only to $u$ and $v'$ is connected only to $v$ to give a new graph $G_e$.
$G_e$ has a Hamiltonian path if and only if $G$ has a Hamiltonian cycle with the edge $e=\{u,v\}$.
Run the Hamiltonian path algorithm on each $G_e$ for each edge $e \in G$. If all graphs have no Hamiltonian path, then $G$ has no Hamiltonian cycle. If at least one $G_e$ has a Hamiltonian path, then $G$ has a Hamiltonian cycle which contains the edge $e$.