Bipartiter Graph/Zerlegung/Numerische Paarungsbedingung/Fakt/Beweis

Beweis

Von (1) nach (2). Da es eine Paarung für gibt, ist die Paarungszahl zumindest . Größer kann die Paarungszahl aber auch nicht sein, da ja jede Paarung Bezug auf die beiden Teile und nimmt. Von (2) nach (1) ist klar. Da man aus einer Paarung für eine injektive Abbildung von nach mit der beschriebenen Kantenbedingung und aus einer solchen Abbildung umgekehrt direkt eine Paarung machen kann, sind (1) und (4) äquivalent. Von (3) nach (4) folgt direkt aus Fakt, wenn man berücksichtigt. Von (4) nach (3) ist trivial.