Matching Augmentation Lemma

Einfache Sprache

Def. Matching Augmentation Lemma

Sei $G=(V,E)$ ein Ungerichteter Graph, $M$ ein matching in $G$, und $P$ ein Augmentierender Kantenzug bzgl. $M$. Dann ist $M'=M\vartriangle P$ ein matching mit $|M'| = |M| + 1$.