Say you have an oracle that can determine (in a polynomial time) if there is a Hamilton path in a certain graph. (Reminder: the Hamilton path problem is in NPC).
Describe how to use the oracle in order to find a Hamilton path in a graph, in a polynomial time.
Any ideas?
A Hamiltonian path visits every vertex exactly once.
If you have an oracle you can test removing each edge in turn. If the oracle says there is still a path then keep the edge deleted, otherwise restore the edge and try the next one.
Once you have gone through all edges, all that will be left will be the Hamiltonian path.