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!