Cardinality-maximal matching

Basic definitions

1. Basic graph definitions
2. Matchings in graphs

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:

1. Classical bipartite cardinality matching (bipartite graphs [math]\displaystyle{ G }[/math] only)
2. Maximum matching by Edmonds

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]. Let [math]\displaystyle{ \Delta:=(M\setminus M')\cup(M'\setminus M) }[/math] denote the symmetric difference of [math]\displaystyle{ M }[/math] and [math]\displaystyle{ M' }[/math]. Obviously, any node [math]\displaystyle{ v\in V }[/math] is incident to at most two edges in [math]\displaystyle{ \Delta }[/math]. Consequently, [math]\displaystyle{ \Delta }[/math] decomposes into node-disjoint paths (some of them may be cycles). These paths are alternating. Since [math]\displaystyle{ |M'|\gt |M| }[/math], at least one of these paths must be augmenting.