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