Problem
COM-B2-M08-P017 Maximum and Augmenting Path
#17
★★★★☆ Level 4 of 5
Prove: if there exists an augmenting path with respect to a matching, then the matching is not maximum in size.
Switch edges along the path.
By definition, an augmenting path starts and ends at uncovered vertices and its edges alternate. Switching the status of edges along the path preserves the matching property and adds one more edge than it removes. Thus the matching size increases by \(1\). Hence the original matching was not maximum in size.
One side of the augmenting path theorem.