I need to prove as an exercise that the following problem is NP-Complete:
- Given a graph and an already existing Hamiltonian Circuit in that graph, decide if the graph has another Hamiltonian Circuit
For the proof I can use the NP-Completeness proof of the Hamiltonian Circuit Problem. I suppose I must reduce the Hamiltonian Circuit Problem to this one, but I can't see how. By the way, the reduction must be done in logarithmic space (L), not in polynomial time (P).