Die Paarungszahl eines bipartiten Graphen ${\displaystyle {}G=A\uplus B}$ ist die größtmögliche Anzahl von Kanten in einer Paarung von ${\displaystyle {}G}$.