Wikipedia link states that you are able to reduce HP to HC by adding a single vertex that is connected with all the edges. I understand the reason why the reduction from cycle to path works by adding 2 vertices, one connected to s and the other to t.
The problem is, I can't seem to find or come up with a solution for why this reduction is wrong or incomplete:
Given a directed graph G with a hamiltonian path from s to t, convert it into a graph H that contains a hamiltonian cycle, by just adding one edge from t to s.
It seems correct at first glance but my professor said that it is incorrect in computation complexity terms and I can't find out why.
Best Answer
Adding a vertex $x$ to an existing graph $G$ and connecting it to all the vertices in $G$ (calling the new graph $H$) works in general: any Hamiltonian cycle in $H$ corresponds to a Hamiltonian path in $G$. So if you can find a Hamiltonian cycle in $H$, this immediately gives you a Hamiltonian path in $G$, and if there are no Hamiltonian cycles in $H$ then there are no Hamiltonian paths in $G$. Hence the conclusion that "finding a Hamiltonian path cannot be significantly slower (in the worst case, as a function of the number of vertices) than finding a Hamiltonian cycle."
Your suggestion of connecting two ends of a Hamiltonian path in $G$ to form $H$ would indeed lead to your $H$ having a Hamiltonian cycle. But it involves finding the ends of the Hamiltonian path in $G$ first before you even know the existence of $H$. The quoted conclusion is based on the other direction: it points to how finding a Hamiltonian cycle in its $H$ leads easily to finding a Hamiltonian path in $G$