Eine Paarung ${\displaystyle {}P\subseteq E}$ in einem Graphen ${\displaystyle {}G}$ heißt perfekt, wenn die Kanten der Paarung jeden Knoten des Graphen abdecken.