Graf nazywamy dwudzielnym jeśli zbiór jego wierzchołków można podzielić na takie dwa rozłączne podzbiory $X$ i $Y$, że każda krawędź grafu ma jeden koniec w $X$ a drugi w $Y$.

Innymi słowy są to wszystkie grafy, których wierzchołki można pokolorować na dwa kolory tak, aby końce każdej krawędzi miały różne kolory.

??? Który z tych grafów jest dwudzielny?

A:
B:

---

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