in a graph is a collection of edges whose ends are disjoint. A maximal matching
is one that cannot be extended to a larger matching; it is easy to find one by adding edges until further addition is not possible. A maximum matching
is a matching containing the largest number of edges among all matchings. An augmenting path
for a matching
is a path with an odd number of edges,
. The symmetric difference of
yields a matching having one more edge than
For the basics of the Hungarian algorithm in the bipartite case, see the Demonstration "The Hungarian Maximum Matching Algorithm". For details of the shrinking process see [1, 3, 4]. The first example is from the notes of Zwick . The second example is interesting because the second blossom uses an edge that arose from the shrinking of the first blossom, but is not an edge in the original graph.
While a recursive approach might not be the most efficient, it does work well for graphs of several thousand vertices. A more efficient implementation of the blossom algorithm that also includes the more difficult case of weighted edges can be found in .
 W. Cook, W. Cunningham, W. Pulleyblank, and A. Schrijver, Combinatorial Optimization,
New York: Wiley, 1998.
 V. Kolmogorov, "Blossom V: A New Implementation of a Minimum Cost Perfect Matching Algorithm," Mathematical Programming Computation 1
(1), 2009 pp. 43–67.