Bipartiter Graph/Zerlegung/Numerische Paarungsbedingung/Fakt/Beweis

Beweis

Von (1) nach (2). Da es eine Paarung für ${}A$ gibt, ist die Paarungszahl zumindest ${}{\#\left(A\right)}$. Größer kann die Paarungszahl aber auch nicht sein, da ja jede Paarung Bezug auf die beiden Teile ${}A$ und ${}B$ nimmt. Von (2) nach (1) ist klar. Da man aus einer Paarung für ${}A$ eine injektive Abbildung von ${}A$ nach ${}B$ 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 ${}N(S)=\bigcup _{s\in S}N(s)$ berücksichtigt. Von (4) nach (3) ist trivial.

Zur bewiesenen Aussage