---
title: "General Matching and Blossoms"
summary: Why odd cycles break the bipartite algorithm, what a blossom is, Edmonds' contraction, and the Tutte/Berge formulas.
difficulty: olympiad
tags: [matching, blossoms, hard]
prereq: [matching/bipartite, matching/konig]
see: [matching/intro, complexity/npc-graphs]
---

## Blossoms: why bipartite logic dies

:::definition label="Blossom"
Given a matching $M$ in an arbitrary graph, a **blossom** is an odd cycle $C$ with $|C| = 2k+1$ together with a vertex $b \in C$ (its *base*) such that the path from $b$ along $C$ in either direction is *alternating* starting with a matched edge... equivalently: $C$ has $k$ matched edges, and the two edges of $C$ incident to $b$ are both unmatched. Contracting $C$ into a single vertex preserves matchings up to one extra matched edge.
:::

:::note title="Why bipartite logic dies on a triangle"
Take $K_3$ with $M = \{uv\}$ and a free vertex $w$. Searching for an augmenting path from $w$: $w \to u$ (unmatched), then from $u$ the only way onward is the *matched* edge $uv$, landing on $v$, and from $v$ the unmatched edge $vw$ returns to the start. The alternating walk is a cycle of odd length — so "reachable" sets become inconsistent: the same vertex is reached at both even and odd distance, and the DFS's `used` marker either loops forever or refuses a legitimate augmentation. Blossoms are exactly these odd cycles; the fix is to **contract** each one, keep searching in the smaller graph, and expand the answer afterwards.
:::

## Edmonds' matching theorem

:::theorem title="Edmonds' matching theorem"
A graph has a perfect matching iff for every $U \subseteq V$, the number of odd components of $G - U$ is at most $|U|$. (Tutte's 1-factor theorem; equivalently, the maximum matching has size $\tfrac12 \min_{U} (n - o(G-U) + |U|)$ — Berge–Edmonds formula.)
:::

:::proof
Necessity: in a perfect matching, each odd component of $G-U$ must send at least one edge into $U$, and those edges are distinct per component, so $|U| \ge o(G-U)$.
Sufficiency: contrapositive via the algorithm — if the search for an augmenting path fails in the maximal-augmentation state, the set $U$ of bases of the blossoms/outer vertices reached by the alternating forest *violates* the condition: every odd component of $G - U$ is a contracted blossom with all its vertices matched internally, and each outer vertex of $U$ accounts for at most one such component. The construction of $U$ from the failed search is the certificate, which is why the theorem is a proof of existence *and* the algorithm's correctness argument at once. ∎
:::

## What to implement, realistically

:::props title="What to implement, realistically"
- **$O(V^3)$ Edmonds with union-find + explicit contraction**: ~70 lines; correct, slow constant; use when $V \le 500$,
- **$O(V E)$ blossom growth without global contraction** (the "labb, maxlab" Gabow style): faster, but 3× the code,
- **randomised algebraic approach**: the Tutte matrix over a large field, rank $= 2 \cdot$ (max matching size); $O(n^\omega)$ with Gaussian elimination, ~25 lines, and it answers "is there a perfect matching", "which edges are allowed", and "the size" with a one-sided error of $2^{-30}$ per trial. This is often the *shortest* correct solution in a contest, at the price of a probabilistic argument you must be able to state,
- **for the special cases**: a tree (DP, @matching/intro problems), a cactus, a planar graph with small faces (Kasteleyn/Pfaffian for counting), or general graphs where maximum matching is only needed for "does a near-perfect matching exist" (then the greedy maximal matching plus a few augmentations usually passes, but has no guarantee — do not rely on it).
:::

```cpp blossom-sketch.cpp
// find-augmenting-path with blossom contraction, O(V*E) per search:
//   base[v], p[v], q = BFS queue of "outer" vertices
//   lca(a, b): walk up via p[] marking used[] to find the blossom base
//   mark_path(v, b, children): walk v up to b, contracting each vertex on the way
//   when an edge (a,b) joins two outer vertices of different trees:
//       if lca(a,b) is undefined -> augment along a + path to root + b
//       else -> blossoms: mark_path(a,b,a), mark_path(b,a,b) and enqueue contracted vertices
int lca(int a, int b) {
    static vector<bool> used(n); fill(used.begin(), used.end(), false);
    for (;;) { a = base[a]; used[a] = true; if (!match[a]) break; a = p[match[a]]; }
    for (;;) { b = base[b]; if (used[b]) return b; b = p[match[b]]; }
}
void mark_path(int v, int b, int children) {
    while (base[v] != b) {
        blossom[base[v]] = blossom[base[match[v]]] = true;
        p[v] = children; children = match[v];
        if (!used[match[v]]) { used[match[v]] = true; q.push(match[v]); }
        v = p[match[v]];
    }
}
```

## The three implementation cliffs

:::warning title="The three implementation cliffs"
1. `lca` must be recomputed **on contracted bases** (`a = base[a]` inside the loop) — using original vertices makes the base wrong and the augmentation invalid;
2. when a blossom is contracted, the *parity* of everything inside flips: the `mark_path` loop must mark **both** endpoints of each matched pair inside the blossom as in-blossom, or the same blossom is rediscovered forever;
3. after finding an augmenting path in the contracted graph you must **expand** blossoms one by one (each expansion rotates the internal matching by one edge) — this post-processing is where a hand-written implementation is more error-prone than the search itself, and it is why many teams prefer the randomised rank method instead.
:::

## Weighted general matching

:::example title="Weighted general matching"
Maximum-weight matching in a general graph = the blossom *algorithm with weights* (Edmonds' primal–dual), $O(V^2 \cdot$ something$)$, and effectively unimplementable in a contest. Two escape routes that are real: (a) if the graph is bipartite, use Hungarian / min-cost flow (@matching/hungarian, @flow/mcmf); (b) if weights are on vertices or the objective is "maximise the number of matched pairs with a bonus", reduce to min-cost flow on a bipartite relaxation and check the relaxation is integral for your instance class. Otherwise the problem is almost certainly not asking for weighted general matching.
:::

:::problems
- [[CSES 1696]] School Dance | https://cses.fi/problemset/task/1696 | easy | re-solve it with a general-graph matching routine and compare the code length
- [[CSES 1130]] Tree Matching | https://cses.fi/problemset/task/1130 | core | a graph where blossoms can never appear: prove the DP is enough because there are no odd cycles
:::