Eine Paarung P ⊆ E {\displaystyle {}P\subseteq E} in einem Graphen G = ( V , E ) {\displaystyle {}G=(V,E)} heißt maximal, wenn jedes P ′ {\displaystyle {}P'} mit P ⊂ P ′ ⊆ E {\displaystyle {}P\subset P'\subseteq E} keine Paarung ist.
