Editing Hamiltonian path problem (section)

== Reductions ==

=== Reduction from the path problem to the cycle problem ===
The problems of finding a Hamiltonian path and a Hamiltonian cycle can be related as follows:

* In one direction, the Hamiltonian path problem for graph ''G'' can be related to the Hamiltonian cycle problem in a graph ''H'' obtained from ''G'' by adding a new [[universal vertex]] ''x'', connecting ''x'' to all vertices of ''G''. Thus, 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. 
* 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 (graph theory)|degree]]-one) vertices ''s'' and ''t'' attached respectively to a vertex v of G and to ''v','' a [[Edge contraction#Vertex cleaving|cleaved copy]] of ''v'' which gives ''v' ''the same neighbourhood as ''v''. The Hamiltonian path in ''H'' running through vertices {{tmath|s-v-x-\cdots-y-v'-t}} corresponds to the Hamiltonian cycle in ''G'' running through {{tmath|v-x-\cdots-y(-v)}}.<ref>[https://math.stackexchange.com/q/1290804 Reduction from Hamiltonian cycle to Hamiltonian path]</ref>