thumb|123px|Przykładowy graf dwudzielny thumb|79px|Pełny graf dwudzielny Graf dwudzielny – graf, którego zbiór wierzchołków można podzielić na dwa rozłączne zbiory tak, że krawędzie nie łączą wierzchołków tego samego zbioru. Równoważnie: graf, który nie zawiera cykli nieparzystej długości. Jeśli pomiędzy wszystkimi parami wierzchołków należących do różnych zbiorów istnieje krawędź, graf taki nazywamy pełnym grafem dwudzielnym lub kliką dwudzielną i oznaczamy gdzie i oznaczają liczności zbiorów wierzchołków.
Pojęcie można uogólnić na trzy (graf trójdzielny) i więcej zbiorów.
Definicja formalna Grafem dwudzielnym nazywamy trójkę gdzie:
oraz
i są zbiorami wierzchołków, to zbiór krawędzi.
Warunki wystarczające dla grafu hamiltonowskiego Sformułowane zostało twierdzenie, które pozwala określić, czy graf dwudzielny jest grafem hamiltonowskim.
Treść twierdzenia Niech będzie grafem dwudzielnym i niech:
będzie podziałem wierzchołków
Jeśli ma cykl Hamiltona, to:
Jeśli ma ścieżkę Hamiltona, to wartości i różnią się co najwyżej o 1.
Dla pełnych grafów dwudzielnych zachodzi też implikacja w lewo, tj.