Watching this lecture from nptel about NP completeness:(adsbygoogle = window.adsbygoogle || []).push({});

http://www.youtube.com/watch?v=76n4BjlL1cs&feature=player_embedded

-We have an algorithm, HC , which given a graph tells us whether or not it has a hamiltonian cycle.

-We want to use it in order to create an algorithm that determines whether an input graph has a hamiltonian path.

If the input has a HC, then it has a HP as well.Okay.

But around 29:00, it is stated:

If the input doesn't have a HC (the output of HC algorithm is a "no"), we add a vertex to it that connects to all other vertices in the graph.If that new gragh G' has a HC, then the original graph G has a HP.

But thinking about this, how bout this example?

edit:in the pic, i meant to say that "graph G doesn't have a HP"

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Hamiltonian path & cycle

**Physics Forums | Science Articles, Homework Help, Discussion**