Ein Graph ist bipartit, wenn seine Knoten in zwei Mengen geteilt werden können, sodass jede Kante zwischen den Mengen verläuft.
Äquivalent: Der Graph enthält keinen Zyklus ungerader Länge.