Edmonds' Blossom Algorithm

Imagine you are a hospital administrator pairing donors with recipients, a scheduler assigning workers to shifts, or a chemist counting the bonds that stabilize a molecule. In each case you are solving a matching problem: partition a set of pairs so that no person (or atom) is used twice, and make the set as large as possible.

For bipartite graphs — two sides, edges only crossing between them — the answer has been known since the 1950s. Augmenting paths do the job: find a path that alternates between unmatched and matched edges, flip them, and the matching grows by one. Repeat until no such path exists.

General graphs break this story. They contain odd cycles — rings of an odd number of vertices — and an augmenting-path search can spiral inside one indefinitely, confusing a matched edge for an unmatched one and missing a valid augmentation altogether.

In 1965, Jack Edmonds published a fix so elegant it became a landmark in the theory of algorithms. He called it the blossom algorithm. The key insight: when the search encounters an odd cycle, shrink it into a single super-node, solve the matching on the contracted graph, then expand the super-node and recover the matching in the original graph. The contraction preserves augmentability — what works on the shrunken graph works on the original — and the whole process runs in polynomial time.

This was the first proof that maximum matching in general graphs is in P (polynomial time), a result that still shapes how we think about the boundary between tractable and intractable problems today. See P vs NP for the broader picture.

The graph below has an odd cycle (the triangle on the right). Click Step to run the augmenting-path search one move at a time. When the search enters the odd cycle you will see the blossom highlighted and contracted into a single super-node. Click Auto to run continuously, or Reset to start over.

<div class="hint">{{hint}}</div>
<svg id="graph" viewBox="0 0 500 300" aria-label="{{graph_aria}}"></svg>
<div class="info" id="info">{{press_step}} <b id="msize">0</b></div>
<div class="btns">
  <button id="stepBtn" type="button">{{btn_step}}</button>
  <button id="autoBtn" type="button">{{btn_auto}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="legend">
  <span class="leg-item"><span class="leg-edge matched"></span> {{leg_matched}}</span>
  <span class="leg-item"><span class="leg-edge augpath"></span> {{leg_augpath}}</span>
  <span class="leg-item"><span class="leg-node blossom-node"></span> {{leg_blossom}}</span>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#graph { width: 100%; max-height: 300px; border: 1px solid #dde3e8; border-radius: 10px; background: #f9fafb; display: block; }
.info { font-size: .92rem; margin: .55rem 0; min-height: 1.6em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 14px system-ui; padding: .4rem .9rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.legend { display: flex; gap: 1rem; flex-wrap: wrap; font-size: .8rem; color: #555; margin-top: .3rem; }
.leg-item { display: flex; align-items: center; gap: .3rem; }
.leg-edge { display: inline-block; width: 22px; height: 3px; border-radius: 2px; }
.leg-edge.matched { background: #e63946; }
.leg-edge.augpath { background: #2a9d8f; }
.leg-node { display: inline-block; width: 14px; height: 14px; border-radius: 50%; background: #f4a261; border: 2px solid #e76f51; }
/* {{c_svg_classes}} */
.node circle { fill: #d8e4ef; stroke: #5a7088; stroke-width: 1.8; transition: fill .25s, stroke .25s; }
.node.matched circle { fill: #fde8ea; stroke: #e63946; }
.node.blossom circle { fill: #fde8c0; stroke: #e76f51; stroke-width: 2.2; }
.node.free circle { fill: #d8e4ef; stroke: #5a7088; }
.node text { font: 700 13px system-ui; fill: #1d3557; pointer-events: none; text-anchor: middle; dominant-baseline: central; }
.edge { stroke: #adb5c4; stroke-width: 2; fill: none; transition: stroke .25s, stroke-width .25s; }
.edge.matched { stroke: #e63946; stroke-width: 3.5; }
.edge.augpath { stroke: #2a9d8f; stroke-width: 3; stroke-dasharray: 6 3; }
.edge.blossom-edge { stroke: #f4a261; stroke-width: 2.5; }
.super-node ellipse { fill: #fde8c0; stroke: #e76f51; stroke-width: 2.2; }
.super-node text { font: 700 12px system-ui; fill: #7c3d12; text-anchor: middle; dominant-baseline: central; }

// Code not found

Notice how the search backtracks correctly after the contraction. Without blossom handling, the algorithm could loop inside the odd cycle and report a matching smaller than the true maximum. With contraction, every step is safe and the process terminates with a maximum matching — no more augmenting paths exist.

Maximum matching in general graphs is solved — it is in P (polynomial time), proven by Jack Edmonds in 1965.

• Augmenting paths alone: for bipartite graphs, alternating-path BFS gives $O(VE)$ (Hopcroft–Karp improves this to $O(E\sqrt{V})$). But on general graphs the search can cycle inside an odd blossom and miss augmentations entirely — without contraction, correctness breaks.
• Edmonds' original algorithm: each blossom contraction shrinks the graph by at least one node, so at most $O(V)$ contractions happen per augmentation, and at most $O(V)$ augmentations are needed, giving $O(V^{3})$ overall.
• Modern improvements: Micali and Vazirani (1980) and later Gabow (1990) pushed the bound to $O(E\sqrt{V})$ using careful data structures — matching the bipartite Hopcroft–Karp bound.
• The landmark significance: before 1965, it was unclear whether maximum matching in general graphs could be solved in polynomial time at all. Edmonds' paper introduced the concept of a "good characterization" (what we now call a certificate) and was one of the seeds of the P vs NP question itself.

Maximum matching also has a perfect-duality theory: Tutte–Berge formula and Tutte's theorem characterize exactly when a perfect matching exists, and these certificates are checkable in polynomial time, putting the problem firmly in both P and co-NP.

Contrast this with graph coloring or clique, where the decision versions are NP-complete: maximum matching is one of the few graph optimization problems that is genuinely easy.

Maximum matching is one of the most widely deployed graph algorithms:

• Organ and kidney exchange: the UNOS kidney-paired donation program uses maximum matching (and its weighted variant) to find the largest possible set of compatible donor–recipient pairs — lives depend on it.
• Scheduling and assignment: matching workers to shifts, students to dorm rooms, or jobs to machines are all weighted matching problems.
• Chemistry and structural biology: the number of perfect matchings in a molecular graph counts the Kekulé structures of a compound, predicting its chemical stability. This is the origin of Tutte's work in the 1940s.
• Network routing and load balancing: optical switching fabrics use matching to decide which input–output pairs to connect each time slot.
• Machine learning: some clustering and data-association algorithms reduce to bipartite or general matching.
• Theoretical computer science: matching is the canonical example of a problem in P with a non-trivial certificate, making it central to the study of P vs NP and randomized algorithms (Schwartz–Zippel for perfect matching via determinants).

The weighted version — maximum weight matching — is equally well-solved (Galil, Micali, Gabow, 1986) and powers competitive pricing, optimal transport and statistical inference.

Edmonds' blossom algorithm is a masterclass in algorithm design: one structural observation — odd cycles can be safely shrunk without losing augmenting paths — turned an apparently intractable problem into a clean polynomial-time procedure.

The algorithm matters not just for its applications but for what it revealed: that a problem can look hard (odd cycles everywhere, infinite search loops) yet admit a polynomial solution once the right invariant is identified. That lesson echoes through every algorithm course today.

The next time you see a hospital transplant list match, a network switch route its packets, or a chemistry paper count molecular bonds, there is a good chance Edmonds' flower is quietly doing the work — contracting blossoms, augmenting paths, and finding the best possible pairing in a world full of odd cycles.