Graf A nie jest dwudzielny, bo zawiera cykl o nieparzystej liczbie wierzchołków. Zauważmy, że wierzchołków leżących na takim cyklu nie da się pokolorować na dwa kolory tak, aby końce każdej krawędzi miały różne kolory.

Graf B jest dwudzielny. Podzbiory, na które dzielimy zbiór wierzchołków grafu, zaznaczono na rysunku innym kształtem.

B:


Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej