34.2-3

Mostre que, se HAM-CYCLE ∈ P, então o problema de listar os vértices de um ciclo hamiltoniano, em ordem, pode ser resolvido em tempo polinomial.

O seguinte algoritmo polinomial lista os vértices de um caminho hamiltoniano, em ordem, caso o grafo G possua um ciclo hamiltoniano:

H <- G
>para cada aresta e de G faça
    se HAM-CYCLE(H - e) então
        H <- H - e
// se G possui ciclo hamiltoniano, neste ponto H se resume a um ciclo hamiltoniano de G
imprime os vértices do ciclo H em ordem