Reduction from Hamiltonian cycle to Hamiltonian path

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.


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$.


This is a reduction from undirected Hamilton Cycle to undirected Hamilton Path. It takes a graph $G$ and returns a graph $f(G)$ such that $G$ has a Hamilton Cycle iff $f(G)$ has a Hamilton Path.

Given a graph $G = (V,E)$ we construct a graph $f(G)$ as follows.

Let $v \in V$ be a vertex of G, and let $v',s,t \notin V$.

We want to make $v'$ a "copy" of $v$, and add vertices of degree one; $s,t$, connected to $v,v'$, respectively. (See Figure 1.)

That is, $f(G)$ has vertices $V\cup \{v',s,t\}$ and edges $E\cup\{(v',w)|(v,w)\in E\}\cup\{(s,v),(v',t),(v,v')\}$.

Now if $G$ has a Hamilton Cycle, we may write it on the form $(v,u),edges,(u',v)$, where $edges$ is some list of edges which must form a simple path $u\ldots u'$ visiting all vertices but $v$. But then, $(s,v),(v,u),edges,(u',v'),(v',t)$ is a Hamilton Path between $s$ and $t$ in $f(G)$.

If on the other hand $f(G)$ has a Hamilton Path, then it must have $s$ and $t$ as endpoints, since they have degree 1. In which case it must (up to reversal) be of the form $(s,v),(v,y),edges',(y',v'),(v',t)$. But then, $G$ has a Hamilton cycle $(v,y),edges',(y',v)$.

Hamilton Cycle to Hamilton Path reduction