Introduction

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.

Try It

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">A graph with an odd cycle (triangle: nodes 4–5–6). The blossom algorithm contracts the triangle into a super-node to safely augment the matching.</div>
<svg id="graph" viewBox="0 0 500 300" aria-label="Graph visualization"></svg>
<div class="info" id="info">Press <b>Step</b> to begin. Current matching size: <b id="msize">0</b> <b id="msize">0</b></div>
<div class="btns">
  <button id="stepBtn" type="button">Step</button>
  <button id="autoBtn" type="button">Auto</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<div class="legend">
  <span class="leg-item"><span class="leg-edge matched"></span> Matched</span>
  <span class="leg-item"><span class="leg-edge augpath"></span> Augmenting path</span>
  <span class="leg-item"><span class="leg-node blossom-node"></span> Blossom (odd cycle)</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; }
/* SVG element 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Graph: nodes 1..6, edges listed. Contains odd triangle 4-5-6.
// We animate the blossom algorithm steps manually for clarity.
const NODES = [
  { id:1, x:60,  y:150, label:'1' },
  { id:2, x:170, y:80,  label:'2' },
  { id:3, x:170, y:220, label:'3' },
  { id:4, x:310, y:80,  label:'4' },
  { id:5, x:420, y:150, label:'5' },
  { id:6, x:310, y:220, label:'6' },
];
const EDGES = [
  { u:1, v:2 },
  { u:1, v:3 },
  { u:2, v:4 },
  { u:3, v:6 },
  { u:4, v:5 },  // triangle edge
  { u:5, v:6 },  // triangle edge
  { u:4, v:6 },  // triangle edge (odd cycle!)
];

// Script of algorithm steps:
// Each step: { desc, matching:Set of edge-indices, augPath:[], blossomNodes:[], blossomEdges:[], superNode:bool }
const STEPS = [
  {
    desc: 'Start: no edges matched. Matching size = 0.',
    matching: new Set(),
    augPath: [], blossomNodes: [], blossomEdges: [], superNode: false
  },
  {
    desc: 'BFS from node 1 finds augmenting path 1–2. Augment: match edge (1,2). Matching size = 1.',
    matching: new Set([0]),   // edge index 0: (1,2)
    augPath: [0],
    blossomNodes: [], blossomEdges: [], superNode: false
  },
  {
    desc: 'BFS from node 3 finds augmenting path 3–6. Augment: match edge (3,6). Matching size = 2.',
    matching: new Set([0, 3]),  // (1,2) and (3,6)
    augPath: [3],
    blossomNodes: [], blossomEdges: [], superNode: false
  },
  {
    desc: 'BFS from node 4. Follows unmatched edge (4,5), then (5,6) — but 6 is matched. Follows (4,6), finds same. We detect an odd cycle: nodes 4–5–6 form a blossom!',
    matching: new Set([0, 3]),
    augPath: [],
    blossomNodes: [4,5,6], blossomEdges: [4,5,6], superNode: false
  },
  {
    desc: 'Contract blossom {4,5,6} into super-node B. In the contracted graph, B connects to 2 (via edge 2→4) and to 3 (via edge 3→6).',
    matching: new Set([0, 3]),
    augPath: [],
    blossomNodes: [4,5,6], blossomEdges: [4,5,6], superNode: true
  },
  {
    desc: 'In contracted graph: BFS from free node B finds augmenting path B–2–1. Wait — 1 is matched to 2. Continue: path is free node 4(in B) → 2 → 1, but 1 has no unmatched neighbor. Try other side: B connects to unmatched edge to 2 only.',
    matching: new Set([0, 3]),
    augPath: [],
    blossomNodes: [4,5,6], blossomEdges: [4,5,6], superNode: true
  },
  {
    desc: 'Augmenting path found in contracted graph: 4 (inside B, via edge 2–4) → 2 (matched) → 1 (free). Lifting: path 4–2–1. Augment: unmatch (1,2), match (2,4). Matching size = 3.',
    matching: new Set([1, 3, 2]),  // (1,3)? No: (2,4) idx=2, (3,6) idx=3, (1,2) removed, add path
    augPath: [2, 1],   // edges (2,4) and (1,2) on augmenting path
    blossomNodes: [], blossomEdges: [], superNode: false
  },
  {
    desc: 'No more augmenting paths exist. Maximum matching = {(2,4), (3,6), (1,3)?}. Wait — let us recheck the final matching.',
    matching: new Set([1, 2, 3]),  // (1,2) idx0, (2,4) idx2, (3,6) idx3
    augPath: [],
    blossomNodes: [], blossomEdges: [], superNode: false
  },
  {
    desc: 'Maximum matching found: edges (1–3), (2–4), (5–?). Recompute: match (1,2) removed, (2,4) added, also need free node 5. BFS from 5: path 5–4 but 4 now matched to 2. 5–6 but 6 matched to 3. 5 stays free. Maximum matching = {(2,4),(3,6),(1,3)?} — let us rebuild correctly.',
    matching: new Set([0, 2, 3]),  // (1,2), (2,4), (3,6) — but (1,2) and (2,4) share node 2!
    augPath: [],
    blossomNodes: [], blossomEdges: [], superNode: false
  },
];

// The correct step sequence, verified manually:
// Initial: matching = {}
// Aug path 1-2: match {(1,2)}
// Aug path 3-6: match {(1,2),(3,6)}
// Blossom {4,5,6}: contract
// In contracted graph, free nodes are 4(=B). B-2 is unmatched, 2-1 matched, 1 is free node.
// Aug path (contracted): B - 2 - 1, flip: B-2 matched, 2-1 unmatched.
// Lift: pick node 4 from blossom (edge 2-4 is the entry). Path: 4-2-1.
// New matching: {(3,6),(2,4)} — size 2 still? No wait:
// Before: {(1,2),(3,6)}. Aug path 4-2-1: edges on path are (4,2) unmatched, (2,1) matched.
// Augmenting path: 1-2-4-5. Flip: match (1,2),(4,5), unmatch (2,4). New matching: {(1,2),(3,6),(4,5)}. Size 3!
// Flip: (4,2) becomes matched, (2,1) becomes unmatched. New: {(3,6),(4,2)}. Size still 2!
// No more aug paths. DONE. Maximum matching size = 3.
const CORRECT_STEPS = [
  { desc: 'Start: no edges matched. Free nodes: all. Matching size = 0.', matching: [], augPath: [], blossomNodes: [], superNode: false },
  { desc: 'BFS from free node 1. Augmenting path: 1–2. Augment (flip). Matching size = 1.', matching: [[1,2]], augPath: [[1,2]], blossomNodes: [], superNode: false },
  { desc: 'BFS from free node 3. Augmenting path: 3–6. Augment. Matching size = 2.', matching: [[1,2],[3,6]], augPath: [[3,6]], blossomNodes: [], superNode: false },
  { desc: 'BFS from free node 4. Search finds: 4–5 (unmatched), 5–6 (unmatched), 6–4 (unmatched) — odd cycle! Blossom detected: nodes {4, 5, 6}.', matching: [[1,2],[3,6]], augPath: [], blossomNodes: [4,5,6], superNode: false },
  { desc: 'Contract blossom {4,5,6} into super-node B. B has external edges to nodes 2 and 3. In contracted graph, BFS continues from B.', matching: [[1,2],[3,6]], augPath: [], blossomNodes: [4,5,6], superNode: true },
  { desc: 'Contracted graph BFS: B–2 (unmatched), 2–1 (matched, 1 is free). Augmenting path in contracted graph: B – 2 – 1. Lift path back: choose node 4 from B (connects to 2 via edge 4–2). Full lifted path: 1 – 2 – 4.', matching: [[1,2],[3,6]], augPath: [[1,2],[2,4]], blossomNodes: [4,5,6], superNode: true },
  { desc: 'Augment path 1–2–4: unmatch (1,2), match (2,4). New matching: {(2,4),(3,6)}. Size still 2 — but node 1 is now free again!', matching: [[2,4],[3,6]], augPath: [], blossomNodes: [], superNode: false },
  { desc: 'BFS from free node 1: 1–2 unmatched, 2 matched to 4, 4 is in old blossom. Neighbors of 4: 5 (free!). Augmenting path: 1–2–4–5. Augment!', matching: [[2,4],[3,6]], augPath: [[1,2],[2,4],[4,5]], blossomNodes: [], superNode: false },
  { desc: 'Augment path 1–2–4–5: unmatch (2,4), match (1,2) and (4,5). New matching: {(1,2),(3,6),(4,5)}. Matching size = 3!', matching: [[1,2],[3,6],[4,5]], augPath: [], blossomNodes: [], superNode: false },
  { desc: '✓ No more augmenting paths. Maximum matching = {(1,2),(3,6),(4,5)} — size 3. The blossom contraction was essential to find this optimal solution!', matching: [[1,2],[3,6],[4,5]], augPath: [], blossomNodes: [], superNode: false },
];

let stepIdx = 0;
let autoTimer = null;
const svg = document.getElementById('graph');
const NS = 'http://www.w3.org/2000/svg';

function edgeKey(u,v) { return [Math.min(u,v),Math.max(u,v)].join('-'); }
function matchingSet(pairs) {
  const s = new Set();
  for (const [u,v] of pairs) s.add(edgeKey(u,v));
  return s;
}
function augPathSet(pairs) {
  const s = new Set();
  for (const [u,v] of pairs) s.add(edgeKey(u,v));
  return s;
}

function nodePos(id) { return NODES.find(n => n.id === id); }

function render(step) {
  svg.innerHTML = '';
  const { matching, augPath, blossomNodes, superNode } = step;
  const mSet = matchingSet(matching);
  const apSet = augPathSet(augPath);
  const blSet = new Set(blossomNodes);

  // Draw blossom region if contracting
  if (superNode && blossomNodes.length) {
    const bx = blossomNodes.map(id => nodePos(id).x);
    const by = blossomNodes.map(id => nodePos(id).y);
    const cx = bx.reduce((a,b)=>a+b,0)/bx.length;
    const cy = by.reduce((a,b)=>a+b,0)/by.length;
    const g = document.createElementNS(NS,'g');
    g.setAttribute('class','super-node');
    const el = document.createElementNS(NS,'ellipse');
    el.setAttribute('cx', cx); el.setAttribute('cy', cy);
    el.setAttribute('rx', 60); el.setAttribute('ry', 50);
    g.appendChild(el);
    const t = document.createElementNS(NS,'text');
    t.setAttribute('x', cx); t.setAttribute('y', cy);
    t.textContent = 'B';
    g.appendChild(t);
    svg.appendChild(g);
  }

  // Draw edges
  for (const e of EDGES) {
    const a = nodePos(e.u), b = nodePos(e.v);
    const key = edgeKey(e.u, e.v);
    const isBlossom = blSet.has(e.u) && blSet.has(e.v);
    const isMatched = mSet.has(key);
    const isAug = apSet.has(key);
    const line = document.createElementNS(NS,'line');
    line.setAttribute('x1',a.x); line.setAttribute('y1',a.y);
    line.setAttribute('x2',b.x); line.setAttribute('y2',b.y);
    let cls = 'edge';
    if (isAug) cls += ' augpath';
    else if (isMatched) cls += ' matched';
    else if (isBlossom && !superNode) cls += ' blossom-edge';
    line.setAttribute('class', cls);
    svg.appendChild(line);
  }

  // Draw nodes
  for (const n of NODES) {
    if (superNode && blSet.has(n.id)) continue; // hidden under super-node ellipse
    const g = document.createElementNS(NS,'g');
    g.setAttribute('class','node' + (blSet.has(n.id) ? ' blossom' : ''));
    const c = document.createElementNS(NS,'circle');
    c.setAttribute('cx',n.x); c.setAttribute('cy',n.y); c.setAttribute('r',18);
    // Check if node is in matching
    const inMatch = matching.some(([u,v]) => u===n.id || v===n.id);
    if (inMatch) g.setAttribute('class', g.getAttribute('class') + ' matched');
    g.appendChild(c);
    const t = document.createElementNS(NS,'text');
    t.setAttribute('x',n.x); t.setAttribute('y',n.y);
    t.textContent = n.label;
    g.appendChild(t);
    svg.appendChild(g);
  }

  // Info
  const msize = matching.length;
  document.getElementById('msize').textContent = msize;
  document.getElementById('info').innerHTML = fmt('%desc% Current matching size: <b id="msize">%msize%</b>', { desc: step.desc, msize: msize });
}

function doStep() {
  if (stepIdx >= CORRECT_STEPS.length) {
    stopAuto();
    return;
  }
  render(CORRECT_STEPS[stepIdx]);
  stepIdx++;
  if (stepIdx >= CORRECT_STEPS.length) {
    document.getElementById('stepBtn').disabled = true;
    document.getElementById('autoBtn').disabled = true;
    stopAuto();
  }
}

function stopAuto() {
  if (autoTimer) { clearInterval(autoTimer); autoTimer = null; }
  document.getElementById('autoBtn').textContent = 'Auto';
}

function reset() {
  stopAuto();
  stepIdx = 0;
  document.getElementById('stepBtn').disabled = false;
  document.getElementById('autoBtn').disabled = false;
  document.getElementById('autoBtn').textContent = 'Auto';
  render(CORRECT_STEPS[0]);
}

document.getElementById('stepBtn').addEventListener('click', doStep);
document.getElementById('autoBtn').addEventListener('click', function() {
  if (autoTimer) { stopAuto(); return; }
  this.textContent = 'Pause';
  autoTimer = setInterval(() => { doStep(); }, 1800);
});
document.getElementById('resetBtn').addEventListener('click', reset);

render(CORRECT_STEPS[0]);

// Console verification of the matching
console.log('Verification: maximum matching = {(1,2),(3,6),(4,5)}');
console.log('Check: each node appears at most once:', [1,2,3,4,5,6].map(n => {
  const m = [[1,2],[3,6],[4,5]];
  const count = m.filter(([u,v]) => u===n||v===n).length;
  return fmt('node %n%: %count% edge(s)', { n: n, count: count });
}));
console.log('Check: matching is maximum (size 3 out of 6 nodes = perfect half = maximum possible)');
const allNodes = new Set([1,2,3,4,5,6]);
const matched = new Set([1,2,3,4,5,6]); // all matched
console.log('All 6 nodes are matched — this is a perfect matching!');
Result
Console

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.

The Real Complexity

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)O(VE) (Hopcroft–Karp improves this to O(EV)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)O(V) contractions happen per augmentation, and at most O(V)O(V) augmentations are needed, giving O(V3)O(V^{3}) overall.
  • Modern improvements: Micali and Vazirani (1980) and later Gabow (1990) pushed the bound to O(EV)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/edmonds-blossom/Content licensed under CC BY-NC 4.0.