Bipartiter Graph/Zerlegung/Numerische Paarungsbedingung/Fakt

Satz über Paarungen in bipartiten Graphen

Es sei ${}G=(V,E)$ ein bipartiter Graph mit einer bipartiten Zerlegung ${}V=A\uplus B$. Dann sind die folgenden Eigenschaften äquivalent.

1. ${}G$ enthält eine Paarung für ${}A$.
2. Die Paarungszahl von ${}G$ ist gleich ${}{\#\left(A\right)}$.
3. Es gilt die Paarungsbedingung für ${}A$, d.h. zu jeder Teilmenge ${}S\subseteq A$ ist ${}{\#\left(S\right)}\leq {\#\left(N(S)\right)}$.
4. Es gibt eine injektive Abbildung

   $\varphi \colon A\longrightarrow B$

   mit ${}(a,\varphi (a))\in E$ für alle ${}a\in A$.

Zum Beweis, Alternativen Beweis erstellen