Back to Graph Theory Series

Blossom Algorithm

September 6, 2026 Wasil Zafar 27 min read

Odd cycles break every bipartite matching trick in this series. Edmonds' answer — shrink each odd cycle down to a single point — solved general matching and, almost as a side effect, helped define what "efficient algorithm" even means.

Contents

  1. A Bit of History
  2. Matching Foundations
  3. Working Principle
  4. Detecting a Blossom
  5. Contract & Lift
  6. Correctness
  7. Complexity Analysis
  8. Implementation
  9. Real-World Applications
  10. Pitfalls & Debugging
  11. Exercises

A Bit of History

Jack Edmonds published "Paths, Trees, and Flowers" in 1965, introducing the Blossom Algorithm to solve maximum matching in general graphs — those that need not be bipartite, extending the theory from Part 16 and the Hopcroft-Karp deep dive, both of which apply only to the bipartite case. The paper is doubly historic: beyond the algorithm itself, Edmonds used it to informally articulate what "efficient algorithm" should mean — polynomial-time computability — a conceptual cornerstone that helped shape the entire later field of computational complexity theory, including the eventual formal definitions of the classes P and NP.

Matching Foundations

A matching $M$ is a set of edges that share no endpoints. A vertex not incident to an edge of $M$ is exposed (or free). The search does not directly hunt for a larger matching; it hunts for a certificate that the current one can grow.

Alternating path

Edges switch status

The path alternates between edges outside $M$ and edges inside $M$. Starting from an exposed vertex, the first edge is unmatched.

Augmenting path

Both endpoints are exposed

Flipping every edge on the path—matched becomes unmatched and vice versa—adds exactly one edge to $M$.

Flipping an augmenting path increases a matching Before the flip, two red matching edges alternate with three teal unmatched edges along a six-vertex path. After the flip, the three formerly unmatched edges are red matching edges. Before · |M| = 2 After · |M| = 3 sabcdt sabcdt flip
The path has one more unmatched edge than matched edge. Symmetric difference $M \triangle P$ turns a matching of size 2 into one of size 3.

Berge's Theorem

A matching is maximum if and only if no augmenting path exists. This converts an optimization problem into a repeated search problem: find one augmenting path, flip it, and repeat.

Working Principle

A bipartite search grows an alternating forest from exposed roots. Its vertices have a parity label:

Outer / even

Even distance from a root

Explore unmatched edges leaving outer vertices. Every exposed root is outer.

Inner / odd

Odd distance from a root

When an inner vertex is matched, immediately add its matched partner as an outer vertex.

In a bipartite graph, an edge between two outer vertices either joins two trees and exposes an augmenting path, or cannot occur within one alternating tree. In a general graph it can occur inside one tree. The two tree paths plus that edge form an odd alternating cycle: a blossom.

Edmonds' move is to contract that entire odd cycle into one super-vertex, continue the search in the smaller graph, and later lift any discovered augmenting path through the original cycle.

Key Insight

An odd cycle has two routes from its base to any chosen exit; exactly one has the alternating parity needed by the surrounding path. Contraction postpones that local choice. Lifting makes it later, once the entry and exit are known.

Detecting a Blossom

Suppose the search scans an unmatched edge $(u,v)$ joining two outer vertices in the same alternating tree. Let $b$ be the lowest common ancestor of $u$ and $v$ after current contractions. The path $b \leadsto u$, edge $(u,v)$, and path $v \leadsto b$ form an odd cycle. Vertex $b$ is its base.

  1. Walk from $u$ and $v$ toward $b$ through alternating-tree parent and matched-partner links.
  2. Mark every base encountered on those two branches as part of the blossom.
  3. Assign all marked vertices the common base $b$ and queue newly exposed outer representatives.
  4. Continue the same breadth-first search on the implicitly contracted graph.

Zoom Out, Then Zoom Back In

From far away, the odd cycle is one junction with several roads entering it. After the global route chooses which roads matter, zoom back in and select the alternating half of the cycle that connects them.

Worked Example: Contract, Search, Lift

Use six vertices $s,a,b,c,d,t$ and current matching $M=\{ab,cd\}$. Vertices $s$ and $t$ are exposed. Edges $bc$, $bd$, and $cd$ form a triangular blossom with base $b$; the alternating tree reaches $b$ through $s-a-b$.

Detecting, contracting, and lifting a blossom A triangle b c d is detected in an alternating tree rooted at s. It contracts to super-vertex B, revealing augmenting path s a B t. Expansion lifts it to s a b d c t and flipping yields a matching of size three. 1 · Detect 2 · Contract 3 · Lift and flip sabcdt odd cycle b–c–d–b; base b saB{b,c,d}t augmenting path s–a–B–t sabcdt lift: s–a–b–d–c–t new M = {sa, bd, ct}
Contraction hides the parity choice inside the triangle. Lifting chooses $b-d-c$, the side that keeps the full path alternating.
s— unmatched —a— matched —b— unmatched —d— matched —c— unmatched —t

Flipping the lifted path replaces $ab$ and $cd$ with $sa$, $bd$, and $ct$. The matching grows from 2 edges to 3, and every vertex is now matched.

Correctness

1. Flipping an augmenting path is safe

Every internal vertex of an augmenting path is incident to one matched and one unmatched path edge. After the flip it still has exactly one matched edge. The exposed endpoints each gain one, so the result is a matching of size $|M|+1$.

2. The blossom lemma preserves the search

Let $B$ be a blossom and $G/B$ the graph formed by contracting it to one vertex. An augmenting path exists in $G$ exactly when one exists in $G/B$. One direction is immediate: contract the portion of a path inside $B$. For the reverse direction, if a contracted path touches the super-vertex, expand $B$ and choose the one of the two routes around its odd cycle whose parity continues the alternating pattern. The blossom base anchors this lift.

3. No augmenting path means maximum

Repeated contraction lets the search either find and lift an augmenting path or prove none exists. Each successful augmentation increases $|M|$, and at most $\lfloor V/2\rfloor$ edges can be matched. When the search finally fails, Berge's theorem certifies that the matching is maximum.

What Contraction Preserves

Contraction does not claim that all vertices of the cycle are interchangeable in every graph problem. It preserves the specific yes/no question needed here: whether an augmenting path exists relative to the current matching.

Complexity Analysis

The array-based implementation below performs at most $O(V)$ augmenting searches. Its repeated scans for bases and contraction membership give the familiar bound:

$$\text{Time: } O(V^3) \qquad \text{Space: } O(V+E)$$

This is a practical teaching implementation for unweighted maximum-cardinality matching. The Micali–Vazirani algorithm improves unweighted general matching to $O(E\sqrt V)$, but is considerably more intricate. Minimum- or maximum-weight matching requires the weighted blossom family, with dual variables and tight-edge conditions; it is not obtained by attaching weights to this BFS.

ProblemTypical algorithmRepresentative bound
Bipartite, unweightedHopcroft–Karp$O(E\sqrt V)$
General, unweightedClassic blossom implementation below$O(V^3)$
General, unweighted (advanced)Micali–Vazirani$O(E\sqrt V)$
General, weightedPrimal–dual weighted blossomDifferent algorithm and invariants

Implementation

The code performs one BFS-style augmenting-path search from each currently exposed root. Contraction is implicit: vertices stay in the original adjacency lists, while base[v] says which super-vertex currently represents them.

StateMeaningInvariant
match[v]Current partner, or -1match[match[v]] == v
p[v]Predecessor in the alternating forestUsed to reconstruct and flip a path
base[v]Representative after contractionsEqual bases belong to one contracted blossom
used[v]Outer vertex queued for BFSOnly outer vertices expand unmatched edges
blossom[v]Temporary contraction markCleared for each newly detected blossom

Scope of These Listings

They solve maximum-cardinality matching in an undirected, unweighted graph. Self-loops should be ignored; parallel edges do not improve cardinality and may be deduplicated. For weighted matching, use a vetted weighted-blossom implementation.

from collections import deque

def blossom_max_matching(n, edges):
    """
    O(V^3) blossom algorithm for unweighted general-graph matching.
    Vertices are 0-indexed; self-loops are ignored.
    Returns match[] where match[v] is v's partner, or -1 if unmatched.
    """
    if n < 0:
        raise ValueError("n must be non-negative")
    adj = [[] for _ in range(n)]
    for u, v in edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("edge endpoint outside 0..n-1")
        if u == v:
            continue
        adj[u].append(v)
        adj[v].append(u)

    match = [-1] * n
    p = [-1] * n      # parent in the alternating tree
    base = [0] * n     # base (root of blossom) for each vertex
    used = [False] * n
    blossom = [False] * n

    def lca(a, b):
        used_path = [False] * n
        u = a
        while True:
            u = base[u]
            used_path[u] = True
            if match[u] == -1:
                break
            u = p[match[u]]
        v = b
        while not used_path[base[v]]:
            v = p[match[v]]
        return base[v]

    def mark_path(v, b, child):
        while base[v] != b:
            blossom[base[v]] = True
            blossom[base[match[v]]] = True
            p[v] = child
            child = match[v]
            v = p[match[v]]

    def find_path(root):
        nonlocal base
        used[:] = [False] * n
        p[:] = [-1] * n
        for i in range(n):
            base[i] = i
        used[root] = True
        q = deque([root])
        while q:
            v = q.popleft()
            for to in adj[v]:
                if base[v] == base[to] or match[v] == to:
                    continue
                if to == root or (match[to] != -1 and p[match[to]] != -1):
                    curbase = lca(v, to)
                    blossom[:] = [False] * n
                    mark_path(v, curbase, to)
                    mark_path(to, curbase, v)
                    for i in range(n):
                        if blossom[base[i]]:
                            base[i] = curbase
                            if not used[i]:
                                used[i] = True
                                q.append(i)
                elif p[to] == -1:
                    p[to] = v
                    if match[to] == -1:
                        return to
                    else:
                        used[match[to]] = True
                        q.append(match[to])
        return -1

    for v in range(n):
        if match[v] == -1:
            u = find_path(v)
            if u != -1:
                while u != -1:
                    pv, ppv = p[u], match[p[u]]
                    match[u] = p[u]
                    match[p[u]] = u
                    u = ppv

    return match

# s=0, a=1, b=2, c=3, d=4, t=5; triangle b-c-d is a blossom.
edges = [(0,1), (1,2), (2,3), (3,4), (4,2), (3,5)]
match = blossom_max_matching(6, edges)
print(match, "size =", sum(v != -1 for v in match) // 2)

// O(V^3) unweighted Blossom Algorithm. Micali-Vazirani's
// O(E*sqrt(V)) refinement is considerably more intricate and is typically used
// only via well-tested libraries in production settings.
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int n;
vector<vector<int>> adj;
vector<int> matchv, p, base;
vector<bool> used, blossomArr;

int lca(int a, int b) {
    vector<bool> usedPath(n, false);
    int u = a;
    while (true) {
        u = base[u];
        usedPath[u] = true;
        if (matchv[u] == -1) break;
        u = p[matchv[u]];
    }
    int v = b;
    while (!usedPath[base[v]]) v = p[matchv[v]];
    return base[v];
}

void markPath(int v, int b, int child) {
    while (base[v] != b) {
        blossomArr[base[v]] = true;
        blossomArr[base[matchv[v]]] = true;
        p[v] = child;
        child = matchv[v];
        v = p[matchv[v]];
    }
}

int findPath(int root) {
    fill(used.begin(), used.end(), false);
    fill(p.begin(), p.end(), -1);
    for (int i = 0; i < n; i++) base[i] = i;
    used[root] = true;
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int to : adj[v]) {
            if (base[v] == base[to] || matchv[v] == to) continue;
            if (to == root || (matchv[to] != -1 && p[matchv[to]] != -1)) {
                int curbase = lca(v, to);
                fill(blossomArr.begin(), blossomArr.end(), false);
                markPath(v, curbase, to);
                markPath(to, curbase, v);
                for (int i = 0; i < n; i++) {
                    if (blossomArr[base[i]]) {
                        base[i] = curbase;
                        if (!used[i]) { used[i] = true; q.push(i); }
                    }
                }
            } else if (p[to] == -1) {
                p[to] = v;
                if (matchv[to] == -1) return to;
                used[matchv[to]] = true;
                q.push(matchv[to]);
            }
        }
    }
    return -1;
}

int main() {
    n = 6;
    adj.assign(n, {});
    vector<pair<int,int>> edges = {{0,1},{1,2},{2,3},{3,4},{4,2},{3,5}};
    for (auto& e : edges) { adj[e.first].push_back(e.second); adj[e.second].push_back(e.first); }
    matchv.assign(n, -1); p.assign(n, -1); base.assign(n, 0);
    used.assign(n, false); blossomArr.assign(n, false);

    for (int v = 0; v < n; v++) {
        if (matchv[v] == -1) {
            int u = findPath(v);
            while (u != -1) {
                int pv = p[u], ppv = matchv[pv];
                matchv[u] = pv; matchv[pv] = u;
                u = ppv;
            }
        }
    }
    for (int v = 0; v < n; v++) cout << v << "->" << matchv[v] << " ";
    cout << endl;
    return 0;
}

// O(V^3) unweighted Blossom Algorithm.
import java.util.*;

class Blossom {
    static int n;
    static List<List<Integer>> adj;
    static int[] matchv, p, base;
    static boolean[] used, blossomArr;

    static int lca(int a, int b) {
        boolean[] usedPath = new boolean[n];
        int u = a;
        while (true) {
            u = base[u];
            usedPath[u] = true;
            if (matchv[u] == -1) break;
            u = p[matchv[u]];
        }
        int v = b;
        while (!usedPath[base[v]]) v = p[matchv[v]];
        return base[v];
    }

    static void markPath(int v, int b, int child) {
        while (base[v] != b) {
            blossomArr[base[v]] = true;
            blossomArr[base[matchv[v]]] = true;
            p[v] = child;
            child = matchv[v];
            v = p[matchv[v]];
        }
    }

    static int findPath(int root) {
        Arrays.fill(used, false);
        Arrays.fill(p, -1);
        for (int i = 0; i < n; i++) base[i] = i;
        used[root] = true;
        Deque<Integer> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            int v = q.poll();
            for (int to : adj.get(v)) {
                if (base[v] == base[to] || matchv[v] == to) continue;
                if (to == root || (matchv[to] != -1 && p[matchv[to]] != -1)) {
                    int curbase = lca(v, to);
                    Arrays.fill(blossomArr, false);
                    markPath(v, curbase, to);
                    markPath(to, curbase, v);
                    for (int i = 0; i < n; i++) {
                        if (blossomArr[base[i]]) {
                            base[i] = curbase;
                            if (!used[i]) { used[i] = true; q.add(i); }
                        }
                    }
                } else if (p[to] == -1) {
                    p[to] = v;
                    if (matchv[to] == -1) return to;
                    used[matchv[to]] = true;
                    q.add(matchv[to]);
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        n = 6;
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[][] edges = {{0,1},{1,2},{2,3},{3,4},{4,2},{3,5}};
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        matchv = new int[n]; p = new int[n]; base = new int[n];
        used = new boolean[n]; blossomArr = new boolean[n];
        Arrays.fill(matchv, -1);

        for (int v = 0; v < n; v++) {
            if (matchv[v] == -1) {
                int u = findPath(v);
                while (u != -1) {
                    int pv = p[u], ppv = matchv[pv];
                    matchv[u] = pv; matchv[pv] = u;
                    u = ppv;
                }
            }
        }
        for (int v = 0; v < n; v++) System.out.print(v + "->" + matchv[v] + " ");
    }
}

Real-World Applications

Christofides' algorithm

Its TSP guarantee requires a minimum-weight perfect matching among odd-degree tree vertices. That invokes the weighted blossom family, not the unweighted listing above.

Any-to-any pairing

When participants are not naturally split into left and right groups, compatibility forms a general graph. Maximum matching finds the largest set of disjoint acceptable pairs.

Molecular graph analysis

Perfect and maximum matchings help model bond-assignment structures in molecular graphs, where odd cycles make bipartite-only methods insufficient.

Graph optimization libraries

General matching is a reusable primitive for factor problems, edge covers, and reductions in combinatorial optimization. Production code typically relies on a vetted implementation.

Which Matching Algorithm Do You Need?

Input structureGoalNatural choice
Bipartite graphMaximum cardinalityHopcroft–Karp
General graphMaximum cardinalityUnweighted blossom
General graph with edge costsMinimum/maximum weightWeighted blossom / primal–dual method
Need only feasibility of a perfect matchingMatch every vertexRun general matching and test $2|M|=V$

Pitfalls & Debugging

Five Common Misreadings

  1. “Every odd cycle is a blossom.” A blossom is an odd alternating cycle relative to the current matching and search forest.
  2. “Contract the graph permanently.” Contractions are search state. After augmentation, rebuild the forest for the changed matching.
  3. “The cycle can be expanded either way.” Only one side has the parity needed to continue the alternating path.
  4. “One contraction is enough.” Blossoms may be nested, overlap across searches, and appear only after earlier contractions.
  5. “Weights are a small extension.” Weighted blossom requires dual feasibility and tight-edge bookkeeping absent here.

Postconditions Worth Testing

  • For every matched vertex $v$, match[match[v]] == v.
  • No vertex is matched to itself, and every reported pair is an input edge.
  • The count sum(match[v] != -1) / 2 equals the number of matching edges.
  • On small random graphs, compare against an exhaustive subset search; this is especially effective for exposing nested-blossom bugs.

Exercises

  1. Flip: verify that symmetric difference with any augmenting path increases the matching size by exactly one.
  2. Trace: for the six-vertex example, label every alternating-tree vertex outer or inner before the triangle contracts.
  3. Lift: show why the alternative route $b-c$ cannot replace $b-d-c$ in the lifted path.
  4. Bipartite case: explain why an edge joining two outer vertices in the same alternating tree would imply an odd cycle.
  5. Testing challenge: generate all simple graphs on at most six vertices and compare the implementation with brute-force maximum matching.

Mental Model to Keep

An odd alternating cycle creates two possible internal routes whose parity is ambiguous too early. Contract the cycle to delay that choice, find the global augmenting path, then expand the cycle and choose the parity-correct route.

Related Deep Dives

Graph Theory Series

Browse all parts of the series plus every algorithm deep dive.

View Full Series
Part 16: Matching Theory

Berge's augmenting-path theorem, extended here from bipartite to general graphs.

Read Article
Hopcroft-Karp Algorithm

The bipartite-only counterpart this algorithm generalizes to arbitrary graphs.

Read Deep Dive