paarer Graph, ein Graph G, der eine Zerlegung der Eckenmenge E(G) in zwei paarweise disjunkte Teilmengen X und Y besitzt (d. h. X∪Y = E(G) und X∩Y = ∅), so daß jede Kante von G mit genau einer Ecke aus X und einer Ecke aus Y inzidiert. Man nennt X, Y Partitionsmengen oder kurz eine Partition bzw. Bipartition von G.

Ist zusätzlich jede Ecke aus X mit jeder Ecke aus Y durch eine Kante verbunden, so spricht man von einem vollständigen bipartiten Graphen, in Zeichen \({k}_{m,n}\), falls \(|X|=n\) und \(|Y|=m\) gilt.

Färbt man in einem bipartiten Graphen G mit der Bipartition X, Y die Eckenmenge X mit einer Farbe und die Eckenmenge Y mit einer weiteren Farbe, so erhält man eine Eckenfärbung von G mit zwei Farben.

Der wichtigste Charakterisierungssatz für bipartite Graphen wurde 1916 von König entdeckt und lautet wie folgt:

Ein Graph ist genau dann bipartit, wenn er keinen Kreis ungerader Länge enthält.

Nach diesem Satz sind z. B. Bäume (Baum) und Wälder (Wald) bipartite Graphen, denn sie besitzen überhaupt keine Kreise.

Da ein Kreis ungerader Länge keine 2-Eckenfärbung hat, ergibt sich aus dem Satz von König, daß ein Graph genau dann bipartit ist, wenn er zweifärbbar ist.