Cardinality-maximal matching
Basic definitions
Definition
Input: An undirected graph [math]\displaystyle{ G=(V,E) }[/math].
Output: A matching [math]\displaystyle{ M }[/math] in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ |M'|\leq|M| }[/math] for any other matching [math]\displaystyle{ M' }[/math] in [math]\displaystyle{ G }[/math].
Known algorithms:
- Maximum matching by Edmonds
- Classical bipartite cardinality matching (bipartite graphs [math]\displaystyle{ G }[/math] only)
Berge's theorem
Statement: A matching [math]\displaystyle{ M }[/math] in an undirected graph [math]\displaystyle{ G=(V,E) }[/math] is cardinality-maximal if, and only if, [math]\displaystyle{ M }[/math] admits no augmenting path.
Proof: Clearly, if [math]\displaystyle{ M }[/math] admits an augmenting path, [math]\displaystyle{ M }[/math] is not cardinality-maximal. So consider the case that [math]\displaystyle{ M }[/math] is not cardinality-maximal. We have to show that [math]\displaystyle{ M }[/math] admits an augmenting path.
By assumption, there is a matching [math]\displaystyle{ M' }[/math] in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ |M'|\gt |M| }[/math]. The symmetric difference, <math>\Delta