# Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle

The following is an excerpt from a material on NP-Theory:
"Let G be an undirected graph and let s and t be vertices in G. A Hamiltonian path in G is a path from s to t using edges of G, on which each vertex of G appears once and only once. By HAM-PATH we denote the problem of determining, given G, s and t, whether G contains a Hamiltonian path from s to t. I now explain a reduction HAM-PATH < HAM-CYCLE. Let G, s, t constitute an input for HAM-PATH. We want to convert it to an input G′ (an undirected graph) for HAM-CYCLE. We add a new vertex u to the vertex set of G in order to obtain the vertex set for G′. The edges of G′ are all the edges of G plus two extra edges (u, s) and (t, u). I leave it to the reader to visualize that G′ contains a Hamiltonian cycle if and only if G contains a Hamiltonian path from s to t."

I am confused as to why do we need to add a vertex u to create G′. Why can't we simply connect s and t and then check for a Hamiltonian Cycle. If it exists, then a path would also exist(as path is a sub-graph of cycle in an undirected graph) and we would be done. What am I missing? I am specially asking this for undirected graphs. I am clear about directed graphs that existence of cycle having s and t does not guarantee Hamiltonian path.
Illustrations or counter examples are welcome!

If the vertex $$u$$ is not added to to $$G'$$, then a Hamiltonian cycle in $$G'$$ does not necessarily correspond to a Hamiltonian path from $$s$$ to $$t$$. This is because the cycle may not have $$s, t$$ adjacent to each other.

For example, one could have Since there is no Hamiltonian path from $$s$$ to $$t$$ in the first graph, there is no Hamiltonian cycle in the second graph. However, if you didn't include $$u$$, then there is a Hamiltonian cycle so the reduction fails.

• Thanks a lot for those clear illustrations!! – Puneet Jul 20 at 4:58

Hint: Suppose that $$G$$ already had a Hamiltonian cycle, but no Hamiltonian path from $$s$$ to $$t$$.

OK, this clearly needs more explanation.

Consider the case of an undirected cycle graph with 4 vertices. This graph, $$G$$, has a Hamiltonian cycle, but it does not have a Hamiltonian path from $$0$$ to $$2$$.

Now add an edge $$(2,0)$$, to obtain a new graph, $$G'$$. This graph obviously has a Hamiltonian cycle, because it has the same one that $$G$$ has. So just because $$G'$$ has a Hamiltonian cycle, that doesn't mean that $$G$$ had the specific Hamiltonian path that you were looking for.

• How is that possible? If I have a Hamiltonian cycle, I will remove the edge between s to t. And I get a Hamiltonian path. Did I miss something? – Puneet Jul 18 at 8:57
• Suppose $G$ is a (directed) cycle graph with 100 vertices. It only has 100 Hamiltonian paths in it. You could add any additional edge to form $G'$, and that graph would have a Hamiltonian cycle. That doesn't mean $G$ had a Hamiltonian path corresponding to that specific added edge. – Pseudonym Jul 18 at 9:45
• I am confused about the undirected case! – Puneet Jul 18 at 14:34
• Got it! Thanks I was not able to visualize this counter example. – Puneet Jul 20 at 4:57