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