Problémy existence hamiltonovské cesty a nejdelší cesty jsou NP-úplné grafové úlohy. Pokud bychom pouze věděli, že je problém hamiltonovské cesty NP-úplný, ale o problému nejdelší cesty tuto informaci neměli, tak tento převod dokazuje NP-úplnost úlohy nejdelší cesty (zároveň je zapotřebí ukázat, že lze ověřit ANO-instanci v polynomiálním čase – stačí posčítat délky jednotlivých hran).

Hamiltonovská cesta

Rozhodovací úloha hamiltonovské cesty se ptá, zda-li lze v daném grafu zkonstruovat cestu takovou, že projde každým vrcholem právě jednou.

Nejdelší cesta

Rozhodovací problém nejdelších cest se ptá, zda-li daný graf obsahuje (acyklickou) cestu délky alespoň k.

Převod

Pro převod úloh stačí dát všem hranám délku 1. Pokud v grafu existuje cesta délky , tak je z definice cesty zřejmé (cesta prochází každým vrcholem maximálně jednou), že je hamiltonovská. Analogicky z opačné strany je hamiltonovská cesta v takovémto grafu nejdelší cestou.