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