Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I've seen a reduction that's done by adding another vertex to the graph and creating a path through that vertex.

Why do I need to add a vertex? Cant I just remove an edge? Lets say the graph with the HamCycle is G,s,t when removing the edge between s and t dont I get a path the goes through all the vertexes that's qualified as a Hamiltonian path?

share|improve this question
Have you tried writing down the reduction without the additional note? What does it look like, where does your proof get stuck? –  Raphael Feb 11 '13 at 12:25
add comment

1 Answer

up vote 4 down vote accepted

First of all I think that the direction of the reduction of your question is from Hampath to Hamcycle (you prove the NP-hardness of Hamcycle reducing the NP-complete problem Hampath to it).

Now given an instance of Hampath: $G,s,t$:

1) there is an edge between $s$ and $t$
2) there is not an edge between $s$ and $t$

In both cases the extra node $u$ is needed in order to force $s,u,t$ to be consecutive nodes in the Hamiltonian cycle.

The new graph $G'$ with a new node $u$ and new edges $(s,u), (u,t)$ (in the first case you split the original edge) will have an Hamiltonian cycle iif the original graph $G$ has an Hamiltonian path from $s$ to $t$.

You can "play" with these two graphs:

enter image description here

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.