Hamiltonian Cycle; Prove: if there's an efficient algorithm to determine that an HC exists, then there's an efficient FIND algorithm

Let G(V,E) be an undirected graph. A Hamiltonian cycle is a cycle that visits each vertex v of G exactly once (except the first vertex, which is also the last vertex in the cycle).

Assume: There Exists an efficient algorithm that determines if a graph has a Hamiltonian cycle (returns True\False). Let's call this alg' D for Determine.

• Prove: There exists an efficient algorithm that returns a Hamiltonian Cycle.

My answer attempt

Assume D(G) = true

Let G'=G (Define G' a copy of G).

For each edge e in E:

    G' = G' \ {e}           // Remove e from G.

    d_boolean = D(G')       // Run D alg' on the new Graph.

    if d_boolean = false
        then G' = G' U {e}  // restore e to graph (because e must be in the Hamiltonian Cycle)

    // else d_boolean=true we do nothing because e is not an edge on the Hamiltonian Cycle

Return G'

My Question

As you can see, I have an idea of an algorithm to show that one exists. I feel it's the right direction... But how do I prove that this algorithm actually returns the Hamiltonian Cycle?

There is just one element missing in your pseudo code: it is not guaranteed that 𝐺 has a Hamilton Cycle.

So you would need to have a first check, before doing anything else, that ensures that it does have a Hamilton Cycle.

If not D(G):
    Return No_Hamilton_Cycle!

Secondly, the algorithm returns a Hamilton Cycle (not the): there can be many alternative Hamilton Cycles in 𝐺, but the order in which you try removing edges, determines which one of those competing Hamilton Cycles you will finally get.

With the above addition, you can be sure that at the start and end of each iteration, 𝐺’ has a Hamilton Cycle: either an iteration will remove an edge and confirm that 𝐺’ still has a Hamilton Cycle, or that removal is undone, so that the state of 𝐺’ is the same at the end as as at the start of that iteration.

When the loop has finished you know that:

1. 𝐺’ has a Hamilton Cycle, because that was true at the end of the last iteration
2. There is no edge you can remove from 𝐺’ and still have a Hamilton Cycle, because you tried removing all those edges without success. Granted, sometimes 𝐺’ still had other edges at that moment of attempt, but that doesn't matter: if an edge is essential for having a Hamilton Cycle in a 𝐺’, then it still is essential after you have removed some other non-essential edges.
3. This algorithm has not added or removed any nodes: 𝐺’ has the same nodes as 𝐺
4. This algorithm has not added any edges: the set of edges of 𝐺’ is a subset of the edges of 𝐺 (possibly equal to it).

From these points we can conclude that if 𝐺 has a Hamilton Cycle, then 𝐺’ is a Hamilton Cycle of 𝐺.