Reduction from Hamiltonian cycle to Hamiltonian path

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

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