[2] Given a general graph G = (V, E), the algorithm finds a matching M such that each vertex in V is incident with at most one edge in M and |M| is maximized.
Unlike bipartite matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph.
[3] A major reason that the blossom algorithm is important is that it gave the first proof that a maximum-size matching could be found using a polynomial amount of computation time.
[4] As elaborated by Alexander Schrijver, further significance of the result comes from the fact that this was the first polytope whose proof of integrality "does not simply follow just from total unimodularity, and its description was a breakthrough in polyhedral combinatorics.
We can formalize the algorithm as follows: We still have to describe how augmenting paths can be found efficiently.
Given G = (V, E) and a matching M of G, a blossom B is a cycle in G consisting of 2k + 1 edges of which exactly k belong to M, and where one of the vertices v of the cycle (the base) is such that there exists an alternating path of even length (the stem) from v to an exposed vertex w. Finding Blossoms: Define the contracted graph G' as the graph obtained from G by contracting every edge of B, and define the contracted matching M' as the matching of G' corresponding to M.
The search for an augmenting path uses an auxiliary data structure consisting of a forest F whose individual trees correspond to specific portions of the graph G. In fact, the forest F is the same that would be used to find maximum matchings in bipartite graphs (without need for shrinking blossoms).
[8] The construction procedure considers vertices v and edges e in G and incrementally updates F as appropriate.
If v is in a tree T of the forest, we let root(v) denote the root of T. If both u and v are in the same tree T in F, we let distance(u,v) denote the length of the unique path from u to v in T. The following four figures illustrate the execution of the algorithm.
First, the algorithm processes an out-of-forest edge that causes the expansion of the current forest (lines B10 – B12).
When G is bipartite, there are no odd cycles in G. In that case, blossoms will never be found and one can simply remove lines B20 – B24 of the algorithm.