Eksempel: Den handelsreisendes problem
Oppgave
Dersom vi vet at alle nodene i en sammenhengende graf har partall grad, hva kan vi konkludere med da?
Vi kan ikke vite om det finnes en hamiltonsti eller ikke basert på denne informasjonen. Det finnes grafer hvor alle nodene har grader som er partall, men hvor det ikke finnes noen hamiltonsti.
Vi kan ikke vite om det finnes en hamiltonsykel eller ikke basert på denne informasjonen. Det finnes grafer hvor alle nodene har grader som er partall, men hvor det ikke finnes noen hamiltonsykel.