Eine Paarung ${\displaystyle {}P\subseteq E}$ in einem Graphen ${\displaystyle {}G}$ heißt optimal, wenn sie unter allen Paarungen von ${\displaystyle {}G}$ die größtmögliche Anzahl von Kanten enthält.