NP-Complete Reductions

(1a)

Hamiltonian Path     Hamiltonian Circuit

Modify your graph by adding another node that has edges to all the nodes in the original graph.

If the original graph has a Hamiltonian Path, the new graph will have a Hamiltonian Circuit: the circuit will run from the new node to the start node of the Path, through all the nodes along the Path, back to the new node.

If the original graph does not have a Hamiltonian Path, there can be no Hamiltonian Circuit in the new graph:
(1) There is obviously not one starting from the new node. (No edge from the new node can lead to a Path through the graph which allows a return to the new node.)
(2) There is no possible Circuit starting from any node in the original graph. This is because, at best, the new node would create a Path, but not a Circuit, in the new graph. If there is no Path in the original, there are at least two "gaps" between nodes that would have to be bridged to create a Circuit. Adding the new node could only, at best, bridge one of these, to create a Path but not a Circuit.

Hamiltonian Circuit     Hamiltonian Path

Modify your graph, say:

and add new nodes thus:

The Start node can be connected to any node in the original graph (in this case N); the AlmostThere node must be connected to all nodes originally connected to N.

If there is a Circuit in the original graph, there will be a Path in the new graph from Start to Finish: follow the Circuit from N to the last node in the Circuit before returning to N (either P, Q or R in the example), then go through AlmostThere to Finish.

If there is no Circuit in the original graph, there can be no Path from N to P, Q or R, so there can be no Path from Start to Finish.