Pokażemy, że problem znalezienia ścieżki dwa razy gorszej od optymalnej dla problemu komiwojażera jest nie łatwiejszy od problemu cyklu Hamiltona, czyli potrafiąc go rozwiązać, potrafimy rozwiązać problem Hamiltona. Skonstruujemy redukcję wielomianową przekształcającą instancję problemu cyklu Hamiltona (dowolny graf nieskierowany) w instancję problemu komiwojażera.
Teraz, jeśli nasz algorytm znalazł rozwiązanie o długości mniejszej niż n, to znalazł cykl Hamiltona w oryginalnym grafie. W przeciwnym przypadku rozwiązanie zawiera co najmniej jedną dodaną krawędź, a więc jest większe niż 2n, czyli rozwiązanie komiwojażera (optymalna ścieżka) jest większe niż n – nie mieści się w oryginalnym grafie ergo nie istnieje w nim cykl Hamiltona.