\displaystyle f(G) = (k,G) gdzie k = \sum_{e \in E(G)} waga(e) + 1
Problem komiwojażera, to pytanie, czy istnieje cykl Hamiltona o wadze mniejszej niż k. Potrafimy tym rozwiązać pytanie o jakikolwiek cykl Hamiltona, jeżeli damy dobre ograniczenie górne. Tutaj tym ograniczeniem jest suma wag krawędzi (każdy cykl Hamiltona nigdy nie będzie miał w sumie większej wagi).