Es sei G {\displaystyle {}G} ein bipartiter Graph mit einer Bipartition V = A ⊎ B {\displaystyle {}V=A\uplus B} und sei C ⊆ A {\displaystyle {}C\subseteq A} . Man sagt, dass C {\displaystyle {}C} die Paarungsbedingung erfüllt, wenn für jede Teilmenge S ⊆ C {\displaystyle {}S\subseteq C} die Beziehung # ( S ) ≤ # ( N ( S ) ) {\displaystyle {}{\#\left(S\right)}\leq {\#\left(N(S)\right)}} gilt.
