Wiki link states that you are able to reduce from HC to HP by vertex cleaving.
In the other direction, the Hamiltonian cycle problem for a graph G is equivalent to the Hamiltonian path problem in the graph H obtained by adding terminal (degree-one) vertices s and t attached respectively to a vertex v of G and to v', a cleaved copy of v which gives v' the same neighbourhood as v.
While, another answer could be,
Just remove one edge along the Hamiltonian Cycle from G, this will construct a G'. There's a Hamiltonian path in G' iff There's a Hamiltonian cycle in G.
It seems intutive and correct, which is not actually. Why is it wrong?
Note: There's an attempt which is not convincing.
Ref Explanation is not convincing because A itself is NOT along the Hamiltonian cycle.
This is untrue, at least in the brief version you gave. Let 𝐺 be the graph with five vertices and five edges that corresponds to the shape of capital letter A. Removing the horizontal crossing edge gives five vertices and four edges that we designate graph 𝐺′. While 𝐺′ has a Hamiltonian path (it is a path), the graph 𝐺 does not have a Hamiltonian cycle.
Thank you!
Best Answer
Good question!
The answer to this question HC to HP is somehow similar with other direction HP to HC. HP to HC
The key question of this statement is that you could not assume such a Hamiltonian Cycle found at the first hand, as we can't know due to its NP nature.
A good example is a Graph G which there is a Hamiltonian Cycle but all vertices all have multiple edges, making you hard to determine which edge to delete.