jeśli:

to ma cykl Hamiltona.

Jeśli i różnią się co najwyżej o 1, to ma ścieżkę Hamiltona.

Dowód Niech oznacza ilość wierzchołków grafu Cykl Hamiltona możemy wyznaczyć, biorąc na przemian wierzchołki leżące w zbiorach i Jeśli:

wyznacza drogę zamkniętą przechodzącą dokładnie raz przez każdy wierzchołek, to

muszą należeć do jednego ze zbiorów podziału, bez straty ogólności załóżmy, że należą one do Ponieważ istnieje krawędź liczba musi być parzysta, a więc wszystkie wierzchołki należą do z czego wynika, że:

W przypadku ścieżki Hamiltona można zastosować podobne wyszukiwanie, zakończyć je na wierzchołku W przypadku, gdy nie jest parzyste, jeden ze zbiorów ma jeden dodatkowy wierzchołek.

Załóżmy jest pełnym grafem dwudzielnym, tj.:

Jeżeli:

to dla każdego „przemiennego” indeksowania wierzchołków wyznacza cykl Hamiltona w Gdy jeden z podziałów, np. jest mniejszy wystarczy wyjść z niego przez