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?The matching $M$ is in gold here and the augmenting path is the one in dotted lines.
Is a matching $M$ maximum iff the graph doesn't have an augmenting path wrt $M$?
matching
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.