Berge's theorem: a matching $M$ is maximum if and only if the graph doesn't have an augmenting path with respect to $M$.

I don't understand this theorem. For instance the following matching is maximum but has an augmenting path, doesn't it?

enter image description here

The matching $M$ is in gold here and the augmenting path is the one in dotted lines.


An augmenting path must alternate between gold and black, starting and ending with black edges. In this way, if you replace the gold edges with the black edges, you obtain a larger matching. This argument shows that a matching can only be maximum if there is no augmenting path, and Berge's theorem states the inverse direction: if a matching has no augmenting path then it is maximum.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.