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