A

*matching* 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,

such that

and

. The symmetric difference of

with

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 [4]. 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 [2].

[1] W. Cook, W. Cunningham, W. Pulleyblank, and A. Schrijver,

*Combinatorial Optimization, *New York: Wiley, 1998.

[2] V. Kolmogorov, "Blossom V: A New Implementation of a Minimum Cost Perfect Matching Algorithm,"

*Mathematical Programming Computation* **1**(1), 2009 pp. 43–67.