Problem
COM-B2-M08-P018 Criterion for a Maximum Matching
Prove that a matching is maximum in size if and only if there is no augmenting path with respect to it.
If there is a larger matching, consider the symmetric difference of the two matchings.
If an augmenting path exists, switching along it increases the matching size, so the matching is not maximum.
Conversely, suppose there is a matching \(M'\) larger than \(M\). Consider the graph consisting of edges that belong to exactly one of \(M\) and \(M'\). In this graph, all degrees are at most \(2\), so its components are paths and cycles with edges from \(M\) and \(M'\) alternating.
Since \(|M'|>|M|\), in some component there are more edges from \(M'\) than from \(M\). A cycle has equal numbers of both types, so this component is a path. It starts and ends with edges from \(M'\), and its endpoints are uncovered by \(M\). Therefore it is an augmenting path with respect to \(M\). This contradicts the absence of augmenting paths.
A strong level 5 problem; important for algorithmic thinking.