Eine Paarung ${\displaystyle {}P\subseteq E}$ in einem Graphen ${\displaystyle {}G}$ heißt Paarung für eine Teilmenge ${\displaystyle {}S\subseteq V}$, wenn jeder Knoten aus ${\displaystyle {}S}$ von einer Kante aus ${\displaystyle {}P}$ abgedeckt wird.