Problem
COM-B2-M08-P010 Augmenting Path
#10
★★★☆☆ Level 3 of 5
Suppose with respect to a matching there is a path that starts and ends at uncovered vertices, and its edges alternate: unchosen, chosen, unchosen, and so on. Prove that the matching size can be increased by \(1\).
Switch the status of all edges of the path.
Remove from the matching the chosen edges of this path and add the unchosen edges of the path. Since the path alternates, the newly chosen edges still have no common endpoints.
The path starts and ends at uncovered vertices, so it has one more unchosen edge than chosen edges. Therefore the matching size increases by \(1\).
Preparation for the maximum matching criterion.