40.05Intermediate / Advanced3 topics18 min2 interactive animations

General matching

In non-bipartite graphs an alternating search can meet itself at an odd cycle. Edmonds' blossom algorithm contracts such cycles and keeps searching, and Tutte's theorem describes exactly when a perfect matching exists.

Learning goals

Explain why the bipartite search fails on odd cycles
Describe blossom contraction and expansion
Run the blossom algorithm on small graphs
State Tutte's theorem and the Tutte-Berge formula

Prerequisites

Matching basics (Lesson 40.01)Bipartite matching (Lesson 40.02)

Roommate pairing, tournament scheduling and many chemistry problems pair elements of a single set, so the graph is not bipartite. Berge's theorem still holds, but the search for an augmenting path breaks on odd cycles. The fix, found by Edmonds in 1965, is one of the landmark algorithms of combinatorial optimisation.

40.05.1

Blossom algorithm overview

The **blossom algorithm** finds a maximum matching in any undirected graph. For every free vertex root it grows an alternating tree: vertices at even depth (the root and the vertices reached through a matching edge) are scanned, and vertices at odd depth are labelled with a parent. If the scan reaches a free vertex, an augmenting path has been found and is flipped. If it meets an edge that joins two even vertices, an odd cycle has been found; the algorithm **contracts** it (next section) and continues.

The Java class below follows the well-known O(V^3) implementation. parent[] stores tree edges, base[v] is the representative of the blossom containing v, and findPath returns the free vertex that ends an augmenting path, or -1. When the path is flipped, the walk goes through parent[] and match[] alternately; blossoms need no special expansion code because parent was rewired when each blossom was contracted.

Run the animation on the default graph 0-1 1-2 2-0 2-3 3-4 4-5. The first search matches 0 with 1. The search from vertex 2 sees the triangle {0, 1, 2} (with 0-1 matched), contracts it into one vertex with base 2, and then finds the free vertex 3. Later 4 is matched with 5, for a maximum matching of size 3. Other presets: “Triangle: one vertex must stay free” shows a blossom that never leads to a path (size 1), and “Bipartite graph” shows that no contraction is needed when there are no odd cycles.

Java

1static class Blossom {
2    final int n;
3    final List<Integer>[] g;
4    final int[] match, parent, base;                                  // base[v]: representative of v's (contracted) blossom
5    final boolean[] inQueue, inBlossom;
6    @SuppressWarnings("unchecked")
7    Blossom(int n, int[][] edges) {
8        this.n = n;
9        g = new List[n];
10        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
11        for (int[] e : edges) { g[e[0]].add(e[1]); g[e[1]].add(e[0]); }
12        match = new int[n]; parent = new int[n]; base = new int[n];
13        inQueue = new boolean[n]; inBlossom = new boolean[n];
14        Arrays.fill(match, -1);
15    }
16    int lca(int a, int b) {                                           // lowest common ancestor of a and b in the alternating tree
17        boolean[] seen = new boolean[n];
18        while (true) { a = base[a]; seen[a] = true; if (match[a] == -1) break; a = parent[match[a]]; }
19        while (true) { b = base[b]; if (seen[b]) return b; b = parent[match[b]]; }
20    }
21    void markPath(int v, int b, int child) {                          // walk from v up to the blossom base b
22        while (base[v] != b) {
23            inBlossom[base[v]] = inBlossom[base[match[v]]] = true;
24            parent[v] = child;
25            child = match[v];
26            v = parent[match[v]];
27        }
28    }
29    int findPath(int root) {                                          // end of an augmenting path from root, or -1
30        Arrays.fill(inQueue, false);
31        Arrays.fill(parent, -1);
32        for (int i = 0; i < n; i++) base[i] = i;
33        inQueue[root] = true;
34        Deque<Integer> queue = new ArrayDeque<>(List.of(root));
35        while (!queue.isEmpty()) {
36            int v = queue.poll();
37            for (int to : g[v]) {
38                if (base[v] == base[to] || match[v] == to) continue;
39                if (to == root || (match[to] != -1 && parent[match[to]] != -1)) {   // an odd cycle: contract the blossom
40                    int cur = lca(v, to);
41                    Arrays.fill(inBlossom, false);
42                    markPath(v, cur, to);
43                    markPath(to, cur, v);
44                    for (int i = 0; i < n; i++) if (inBlossom[base[i]]) {
45                        base[i] = cur;
46                        if (!inQueue[i]) { inQueue[i] = true; queue.add(i); }
47                    }
48                } else if (parent[to] == -1) {
49                    parent[to] = v;
50                    if (match[to] == -1) return to;                   // a free vertex: augmenting path found
51                    inQueue[match[to]] = true;
52                    queue.add(match[to]);
53                }
54            }
55        }
56        return -1;
57    }
58    int maxMatching() {
59        int size = 0;
60        for (int root = 0; root < n; root++) {
61            if (match[root] != -1) continue;
62            int end = findPath(root);
63            if (end == -1) continue;
64            size++;
65            while (end != -1) {                                       // flip the path, expanding blossoms through parent[]
66                int pv = parent[end], next = match[pv];
67                match[end] = pv;
68                match[pv] = end;
69                end = next;
70            }
71        }
72        return size;
73    }
74}

Worst

O(V³) for this implementation (O(E · √V) with Micali-Vazirani)

Space

O(V + E)

Edmonds' blossom algorithm: maximum matching in a general graph

Interactive · edit the input

undirected graph · 6 vertices · 6 edges

free

Root of the searchInside the contracted blossomMatched vertex or edgeAugmenting pathTree edge

mate of each vertex

free0

free1

free2

free3

free4

free5

base of each vertex (blossom representative)

Setup

In a general graph an alternating search can meet itself at an odd cycle. The blossom algorithm contracts such a cycle into one vertex and keeps searching; this is what makes augmenting-path search correct beyond bipartite graphs.

Step 1 / 14

Java

1static class Blossom {
2    final int n;
3    final List<Integer>[] g;
4    final int[] match, parent, base;                                  // base[v]: representative of v's (contracted) blossom
5    final boolean[] inQueue, inBlossom;
6    @SuppressWarnings("unchecked")
7    Blossom(int n, int[][] edges) {
8        this.n = n;
9        g = new List[n];
10        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
11        for (int[] e : edges) { g[e[0]].add(e[1]); g[e[1]].add(e[0]); }
12        match = new int[n]; parent = new int[n]; base = new int[n];
13        inQueue = new boolean[n]; inBlossom = new boolean[n];
14        Arrays.fill(match, -1);
15    }
16    int lca(int a, int b) {                                           // lowest common ancestor of a and b in the alternating tree
17        boolean[] seen = new boolean[n];
18        while (true) { a = base[a]; seen[a] = true; if (match[a] == -1) break; a = parent[match[a]]; }
19        while (true) { b = base[b]; if (seen[b]) return b; b = parent[match[b]]; }
20    }
21    void markPath(int v, int b, int child) {                          // walk from v up to the blossom base b
22        while (base[v] != b) {
23            inBlossom[base[v]] = inBlossom[base[match[v]]] = true;
24            parent[v] = child;
25            child = match[v];
26            v = parent[match[v]];
27        }
28    }
29    int findPath(int root) {                                          // end of an augmenting path from root, or -1
30        Arrays.fill(inQueue, false);
31        Arrays.fill(parent, -1);
32        for (int i = 0; i < n; i++) base[i] = i;
33        inQueue[root] = true;
34        Deque<Integer> queue = new ArrayDeque<>(List.of(root));
35        while (!queue.isEmpty()) {
36            int v = queue.poll();
37            for (int to : g[v]) {
38                if (base[v] == base[to] || match[v] == to) continue;
39                if (to == root || (match[to] != -1 && parent[match[to]] != -1)) {   // an odd cycle: contract the blossom
40                    int cur = lca(v, to);
41                    Arrays.fill(inBlossom, false);
42                    markPath(v, cur, to);
43                    markPath(to, cur, v);
44                    for (int i = 0; i < n; i++) if (inBlossom[base[i]]) {
45                        base[i] = cur;
46                        if (!inQueue[i]) { inQueue[i] = true; queue.add(i); }
47                    }
48                } else if (parent[to] == -1) {
49                    parent[to] = v;
50                    if (match[to] == -1) return to;                   // a free vertex: augmenting path found
51                    inQueue[match[to]] = true;
52                    queue.add(match[to]);
53                }
54            }
55        }
56        return -1;
57    }
58    int maxMatching() {
59        int size = 0;
60        for (int root = 0; root < n; root++) {
61            if (match[root] != -1) continue;
62            int end = findPath(root);
63            if (end == -1) continue;
64            size++;
65            while (end != -1) {                                       // flip the path, expanding blossoms through parent[]
66                int pv = parent[end], next = match[pv];
67                match[end] = pv;
68                match[pv] = end;
69                end = next;
70            }
71        }
72        return size;
73    }
74}

Live state

0 blossoms0 augmentations

edges

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L1	n=6 edges=6	In a general graph an alternating search can meet itself at an odd cycle. The blossom algorithm contracts such a cycle into one vertex and keeps searching; this is what makes augmenting-path search correct beyond bipartite graphs.
2	L33	root=0	Grow an alternating tree from the free vertex 0. Even vertices (reached by a matching edge, or the root) are scanned; odd ones are only labelled.
3	L50	v=0 to=1	1 is free: the alternating path from 0 ends here (blossoms are expanded through parent[] when the path is flipped).
4	L64	size=1	The path is flipped: the matching grows to 1.
5	L33	root=2	Grow an alternating tree from the free vertex 2. Even vertices (reached by a matching edge, or the root) are scanned; odd ones are only labelled.
6	L49	v=2 to=1 mate=0	Label 1 odd (parent 2); its mate 0 becomes an even vertex and is queued.
7	L40	v=2 to=0 base=2 blossom=0,1	Edge 2-0 joins two even vertices of the tree, closing an odd cycle. Contract it: vertices {0, 1} now share the base 2 and every odd vertex in it becomes even (it joins the queue).
8	L50	v=2 to=3	3 is free: the alternating path from 2 ends here (blossoms are expanded through parent[] when the path is flipped).
9	L64	size=2	The path is flipped: the matching grows to 2.
10	L33	root=4	Grow an alternating tree from the free vertex 4. Even vertices (reached by a matching edge, or the root) are scanned; odd ones are only labelled.
11	L49	v=4 to=3 mate=2	Label 3 odd (parent 4); its mate 2 becomes an even vertex and is queued.
12	L50	v=4 to=5	5 is free: the alternating path from 4 ends here (blossoms are expanded through parent[] when the path is flipped).
13	L64	size=3	The path is flipped: the matching grows to 3.
14	L72	return=3 blossoms=1 augmentations=3	Maximum matching size 3 (0 vertices stay free), with 1 blossom contracted along the way.

40.05.2

Odd-cycle contraction

A **blossom** is an odd cycle of length 2k + 1 containing exactly k matching edges, reached from the tree through its **base**, the one cycle vertex not matched inside the cycle. Every vertex of a blossom can be reached from the base by an alternating path of even length in two ways, one around each side of the cycle. That is why all its vertices behave like even vertices once the blossom is found.

**Contracting** a blossom replaces its vertices by one super-vertex. The key lemma is that the original graph has an augmenting path (relative to the matching) exactly when the contracted graph has one relative to the contracted matching. So the search can safely continue in the smaller graph, and when a path is found it is expanded back into the original cycle, choosing the way around the cycle that makes the alternation work.

In the code the contraction is done lazily: lca finds the base, markPath marks the vertices on both sides and rewires parent so that either way round is alternating, and base[i] = cur merges them. Odd vertices of the blossom become even and join the queue. Bipartite graphs have no odd cycles at all, which is why the plain alternating BFS of the previous lessons is enough for them. The check below tests that condition with a 2-colouring: false means the graph contains an odd cycle, so a blossom is possible.

Vertex label in the tree	How it is reached	What the search does with it
Even (root or mate of an odd vertex)	root, or the matching edge from an odd vertex	scan its edges
Odd	non-matching edge from an even vertex	label with parent, queue its mate
Inside a blossom	merged by contraction	treated as even; shares one base
Free and reached as odd	non-matching edge	end of an augmenting path

Java

1static boolean isBipartite(int n, List<Integer>[] adj) {              // false means an odd cycle exists
2    int[] colour = new int[n];                                        // 0 = unseen; 1 and 2 are the two sides
3    for (int s = 0; s < n; s++) {
4        if (colour[s] != 0) continue;
5        colour[s] = 1;
6        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
7        while (!queue.isEmpty()) {
8            int u = queue.poll();
9            for (int v : adj[u]) {
10                if (colour[v] == colour[u]) return false;             // an edge inside one side closes an odd cycle
11                if (colour[v] == 0) { colour[v] = 3 - colour[u]; queue.add(v); }
12            }
13        }
14    }
15    return true;
16}

Edmonds' blossom algorithm: maximum matching in a general graph

Interactive · edit the input

undirected graph · 6 vertices · 6 edges

free

Root of the searchInside the contracted blossomMatched vertex or edgeAugmenting pathTree edge

mate of each vertex

free0

free1

free2

free3

free4

free5

base of each vertex (blossom representative)

Setup

Step 1 / 14

Java

1static class Blossom {
2    final int n;
3    final List<Integer>[] g;
4    final int[] match, parent, base;                                  // base[v]: representative of v's (contracted) blossom
5    final boolean[] inQueue, inBlossom;
6    @SuppressWarnings("unchecked")
7    Blossom(int n, int[][] edges) {
8        this.n = n;
9        g = new List[n];
10        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
11        for (int[] e : edges) { g[e[0]].add(e[1]); g[e[1]].add(e[0]); }
12        match = new int[n]; parent = new int[n]; base = new int[n];
13        inQueue = new boolean[n]; inBlossom = new boolean[n];
14        Arrays.fill(match, -1);
15    }
16    int lca(int a, int b) {                                           // lowest common ancestor of a and b in the alternating tree
17        boolean[] seen = new boolean[n];
18        while (true) { a = base[a]; seen[a] = true; if (match[a] == -1) break; a = parent[match[a]]; }
19        while (true) { b = base[b]; if (seen[b]) return b; b = parent[match[b]]; }
20    }
21    void markPath(int v, int b, int child) {                          // walk from v up to the blossom base b
22        while (base[v] != b) {
23            inBlossom[base[v]] = inBlossom[base[match[v]]] = true;
24            parent[v] = child;
25            child = match[v];
26            v = parent[match[v]];
27        }
28    }
29    int findPath(int root) {                                          // end of an augmenting path from root, or -1
30        Arrays.fill(inQueue, false);
31        Arrays.fill(parent, -1);
32        for (int i = 0; i < n; i++) base[i] = i;
33        inQueue[root] = true;
34        Deque<Integer> queue = new ArrayDeque<>(List.of(root));
35        while (!queue.isEmpty()) {
36            int v = queue.poll();
37            for (int to : g[v]) {
38                if (base[v] == base[to] || match[v] == to) continue;
39                if (to == root || (match[to] != -1 && parent[match[to]] != -1)) {   // an odd cycle: contract the blossom
40                    int cur = lca(v, to);
41                    Arrays.fill(inBlossom, false);
42                    markPath(v, cur, to);
43                    markPath(to, cur, v);
44                    for (int i = 0; i < n; i++) if (inBlossom[base[i]]) {
45                        base[i] = cur;
46                        if (!inQueue[i]) { inQueue[i] = true; queue.add(i); }
47                    }
48                } else if (parent[to] == -1) {
49                    parent[to] = v;
50                    if (match[to] == -1) return to;                   // a free vertex: augmenting path found
51                    inQueue[match[to]] = true;
52                    queue.add(match[to]);
53                }
54            }
55        }
56        return -1;
57    }
58    int maxMatching() {
59        int size = 0;
60        for (int root = 0; root < n; root++) {
61            if (match[root] != -1) continue;
62            int end = findPath(root);
63            if (end == -1) continue;
64            size++;
65            while (end != -1) {                                       // flip the path, expanding blossoms through parent[]
66                int pv = parent[end], next = match[pv];
67                match[end] = pv;
68                match[pv] = end;
69                end = next;
70            }
71        }
72        return size;
73    }
74}

Live state

0 blossoms0 augmentations

edges

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L1	n=6 edges=6	In a general graph an alternating search can meet itself at an odd cycle. The blossom algorithm contracts such a cycle into one vertex and keeps searching; this is what makes augmenting-path search correct beyond bipartite graphs.
2	L33	root=0	Grow an alternating tree from the free vertex 0. Even vertices (reached by a matching edge, or the root) are scanned; odd ones are only labelled.
3	L50	v=0 to=1	1 is free: the alternating path from 0 ends here (blossoms are expanded through parent[] when the path is flipped).
4	L64	size=1	The path is flipped: the matching grows to 1.
5	L33	root=2	Grow an alternating tree from the free vertex 2. Even vertices (reached by a matching edge, or the root) are scanned; odd ones are only labelled.
6	L49	v=2 to=1 mate=0	Label 1 odd (parent 2); its mate 0 becomes an even vertex and is queued.
7	L40	v=2 to=0 base=2 blossom=0,1	Edge 2-0 joins two even vertices of the tree, closing an odd cycle. Contract it: vertices {0, 1} now share the base 2 and every odd vertex in it becomes even (it joins the queue).
8	L50	v=2 to=3	3 is free: the alternating path from 2 ends here (blossoms are expanded through parent[] when the path is flipped).
9	L64	size=2	The path is flipped: the matching grows to 2.
10	L33	root=4	Grow an alternating tree from the free vertex 4. Even vertices (reached by a matching edge, or the root) are scanned; odd ones are only labelled.
11	L49	v=4 to=3 mate=2	Label 3 odd (parent 4); its mate 2 becomes an even vertex and is queued.
12	L50	v=4 to=5	5 is free: the alternating path from 4 ends here (blossoms are expanded through parent[] when the path is flipped).
13	L64	size=3	The path is flipped: the matching grows to 3.
14	L72	return=3 blossoms=1 augmentations=3	Maximum matching size 3 (0 vertices stay free), with 1 blossom contracted along the way.

40.05.3

Tutte theorem overview

**Tutte's theorem** characterises perfect matchings in any graph: G has a perfect matching if and only if for every subset U of vertices, the graph G − U has at most |U| connected components with an **odd** number of vertices. A set U that breaks the condition is a certificate that no perfect matching exists: each odd component needs one of its own vertices matched to something in U, and U is too small.

The **Tutte-Berge formula** gives the exact size of a maximum matching: ν(G) = (n − max over U of (odd(G − U) − |U|)) / 2. The quantity in the maximum is the number of vertices that must stay free (the deficiency). The code below evaluates the formula by brute force over all subsets, which is exponential and meant only for understanding and for testing the blossom algorithm on small graphs.

When the blossom algorithm stops, it essentially hands over such a certificate: the odd vertices of its final alternating forests form a set U whose removal leaves the odd components that explain the unmatched vertices. So Tutte's theorem plays for general graphs the role that Hall's theorem and König's theorem play for bipartite ones.

Graph	Best U	odd(G − U) − \|U\|	Maximum matching
Triangle	∅	1 − 0 = 1	(3 − 1) / 2 = 1
Path with 4 vertices	∅	0	4 / 2 = 2
Star with 3 leaves	centre	3 − 1 = 2	(4 − 2) / 2 = 1
Even cycle	∅	0	n / 2

Java

1// adj[v] = bit mask of the neighbours of v (n <= 16).
2// Tutte-Berge: maximum matching = (n - max over U of (odd(G - U) - |U|)) / 2, where odd counts odd-sized components.
3static int maxMatchingByTutteBerge(int n, int[] adj) {
4    int deficiency = 0;
5    for (int removed = 0; removed < (1 << n); removed++) {
6        int odd = 0, left = ((1 << n) - 1) & ~removed;
7        while (left != 0) {                                           // peel off one component of G - removed at a time
8            int comp = left & -left, frontier = comp;
9            while (frontier != 0) {
10                int v = Integer.numberOfTrailingZeros(frontier);
11                frontier &= frontier - 1;
12                int fresh = adj[v] & left & ~comp;
13                comp |= fresh;
14                frontier |= fresh;
15            }
16            left &= ~comp;
17            if (Integer.bitCount(comp) % 2 == 1) odd++;
18        }
19        deficiency = Math.max(deficiency, odd - Integer.bitCount(removed));
20    }
21    return (n - deficiency) / 2;
22}

Practice ladder

Now try it yourself

Easy

Find Center of Star Graph

Medium

Possible Bipartition

Advanced

Maximum Students Taking Exam

Key takeaways

An odd cycle (blossom) breaks the bipartite search; contract it and continue.
A graph has an augmenting path iff its contraction has one, so contraction is safe.
Tutte: no perfect matching iff some U leaves more than |U| odd components; Tutte-Berge gives the exact maximum.