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