From the following link:
So basically, in our iff proof, we have to show two directions:
Forward: If Hamiltonian Path has a yes-instance, so does longest path. This makes sense because we can just let “k” = |V| – 1 if hamiltonian path is yes. Then clearly there is a longest simple path with |V| – 1 edges.
I’m having trouble with the backward part
Backward: If Longest Path has a yes instance, so does longest path. Let’s assume that there is a longest path from s to t of length k (this can be a different k than the one we defined above?). How does that guarantee that there is a hamiltonian path from s-t? If it is the same k, where k = |V| – 1, then I agree there is a hamiltonian path, but what if this k is something different?