Maximum matching by Edmonds

Abstract view

Invariant: The current selection [math]\displaystyle{ M }[/math] of edges is a matching.

Variant: Either the cardinality of [math]\displaystyle{ M }[/math] increases, or the number of nodes of [math]\displaystyle{ G }[/math] decreases.

Break condition: There is no more augmenting path.

Definition: A blossom is a cycle [math]\displaystyle{ C }[/math] of odd lengths in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ \lfloor|C|/2\rfloor\lt \math\gt edges on \lt math\gt C }[/math] are matched and the remaining node is matched as well.

Induction basis

Abstract view: Start with some matching, for example, the empty matching.

Induction step

Apply the