Watching this lecture from nptel about NP completeness: 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"