General Matchings

Twelve students and six double rooms

A residence hall has twelve students and six double rooms. The students have said who they would share with: thirteen pairs, written as edges of a graph $L$ on the vertices $s,a,b,c,d,e,f,p,q,t,u,w$. Five rooms are already assigned: $a$ with $b$, $c$ with $d$, $e$ with $f$, $p$ with $q$ and $u$ with $w$. Students $s$ and $t$ have no room, and they did not agree to share with each other.

Can the hall reshuffle the rooms so that all twelve students get one? And if it can't, what could it show the two students left over, to convince them that nobody was careless?

A set of edges in which no vertex appears twice is a matching, and a vertex on none of its edges is exposed. The question asks for a maximum matching in a graph with no two sides. Network Flow and Matchings matched people to jobs through a flow network; here any student may share with any other, so there is no source side and no sink side. This module assumes that module: augmenting paths, and answers that come with a certificate.

L = {}
for pair in "s-a a-b b-c c-d d-e e-f f-b c-p p-q q-t t-u u-w w-a".split():
    x, y = pair.split("-")
    L.setdefault(x, set()).add(y)
    L.setdefault(y, set()).add(x)

def edge(x, y):
    return frozenset((x, y))

M = {edge(*r) for r in ("ab", "cd", "ef", "pq", "uw")}

def is_matching(G, edges):
    ends = [v for e in edges for v in e]
    return (len(ends) == len(set(ends))
            and all(y in G[x] for x, y in map(tuple, edges)))

assert len(L) == 12 and sum(map(len, L.values())) == 2 * 13
assert is_matching(L, M)
assert sorted(v for v in L if not any(v in e for e in M)) == ["s", "t"]

Paths that improve a matching

The tool from Network Flow and Matchings carries over. A path is alternating for $M$ if its edges are in turn outside and inside $M$. It is augmenting if it is also simple, joins two different exposed vertices, and so starts and ends with an edge outside $M$. Swapping the path's edges in and out, $M\oplus P$, gives a matching with one more edge: every inner vertex of the path trades one matched edge for another, and the two exposed ends each gain one.

Proof. If an augmenting path exists, $M\oplus P$ is larger, so $M$ is not maximum. Conversely, suppose some matching $M^{*}$ has more edges than $M$. In $M\oplus M^{*}$ every vertex has at most one edge from each, so each connected piece is a path or a cycle whose edges alternate between $M$ and $M^{*}$. A cycle alternates, so it has as many edges of each. $M^{*}$ has more edges overall, so some piece has more $M^{*}$ edges than $M$ edges. That piece is a path that starts and ends with an $M^{*}$ edge, and its two ends are exposed in $M$: each end has no second edge in the piece, and an $M$ edge at that end would belong to the piece. So it is augmenting for $M$. $◻$

So the algorithm is the same loop as in any graph: find an augmenting path, flip it, repeat. $L$ has a perfect matching, so an augmenting path for $M$ exists:

def maximum(G):
    """Size of a maximum matching, by trying every choice (small graphs only)."""
    def best(free):
        v = min(free, default=None)
        if v is None:
            return 0
        rest = free - {v}
        return max([best(rest)] + [1 + best(rest - {w}) for w in G[v] & rest])
    return best(frozenset(G))

assert maximum(L) == 6 == len(M) + 1

The difficulty is finding the path.

The augmenting-path search, and where it goes wrong

In a bipartite graph the search grows in layers from an exposed vertex $r$. Label $r$ even. From an even vertex $x$, look at each neighbour $y$. If $y$ is exposed, the path to $y$ is augmenting. If $y$ is unlabelled, label it odd and label its partner even. A vertex keeps the first label it gets. On a bipartite graph that is safe: the side of a vertex decides the parity of every path from $r$ to it, so no vertex could deserve both labels.

Run it on $L$ from $s$. Then $a$ is odd and $b$ even. Both $c$ and $f$ are neighbours of $b$, so both become odd, and their partners $d$ and $e$ become even. Now the search is stuck. The edge $c$–$p$ leaves $c$, but $c$ is odd, and from an odd vertex the search only follows the matched edge back. From $t$ it fails in the same way: $a$ is labelled odd from $w$ at the third layer, long before the path around the other side could reach $a$ as an even vertex.

This failure does not depend on luck. The block below runs the layered search in every order of scanning neighbours (every permutation at every vertex), from both exposed vertices:

from itertools import permutations, product

def layered_search(G, M, r, order):
    """The search from Network Flow and Matchings: the first label wins."""
    mate = {v: w for e in M for v, w in (tuple(e), tuple(e)[::-1])}
    label, queue = {r: "even"}, [r]
    while queue:
        x = queue.pop(0)
        for y in order[x]:
            if y in label:
                continue
            if y not in mate:
                return True
            label[y], label[mate[y]] = "odd", "even"
            queue.append(mate[y])
    return False

names = sorted(L)
orders = [dict(zip(names, pick))
          for pick in product(*(permutations(sorted(L[v])) for v in names))]
assert len(orders) == 6 ** 3 * 2 ** 8          # 55,296 scan orders
assert not any(layered_search(L, M, r, o) for r in "st" for o in orders)

The picture shows what went wrong. The edge $d$–$e$ joins two even vertices, which never happens in a bipartite graph, and closes the cycle $b,c,d,e,f$ of length 5. Going round it the other way, $s,a,b,f,e,d,c$ reaches $c$ by an even path ending in a matched edge, and $c$–$p$–$q$–$t$ finishes an augmenting path. With odd cycles, "odd" and "even" describe a path, not a vertex, and the first path found is not always the useful one.

Blossoms, and the idea of shrinking them

Search from all exposed vertices at once. Each exposed vertex is the root of a tree, and the trees together form an alternating forest. An even vertex $x$ scans its neighbours $y$:

• $y$ unlabelled: $y$ is matched (every exposed vertex is a root), so label $y$ odd with parent $x$ and its partner even with parent $y$. The trees grow.
• $y$ even, in a different tree: the path from the root of $x$'s tree to $x$, the edge $x$–$y$, and the path from $y$ to its root is augmenting. Stop.
• $y$ even, in the same tree: the edge $x$–$y$ and the two tree paths up to where they meet form an odd cycle.
• $y$ odd: nothing to do.

The odd cycle in the third case is a blossom. It has $2k+1$ vertices and $k$ matched edges. The vertex where the two tree paths meet is its base. The base is even, and it is the one vertex of the cycle whose matched edge, if it has one, leaves the cycle. The tree path from the root to the base is the stem.

Every vertex of a blossom is reachable from the root by an even alternating path: down the stem to the base, then round the cycle in the direction that starts with an unmatched edge. So every vertex of the blossom deserves to be even. Edmonds' algorithm (1965) makes that true by shrinking the blossom into one new even vertex, adjacent to every neighbour of the cycle. It takes over the base's matched edge and place in the tree, and the $k$ matched edges inside the cycle disappear. The search carries on in the smaller graph $G/B$, and a path found there is lifted back into $G$ through each shrunk blossom, newest first.

Edmonds' search on the twelve students

Take the rule "breadth first; roots, and each vertex's neighbours, in alphabetical order". The roots are $s$ and $t$. From $s$: $a$ becomes odd and $b$ even. From $t$: $q$ odd and $p$ even, then $u$ odd and $w$ even. From $b$: $c$ odd and $d$ even, then $f$ odd and $e$ even. $p$ and $w$ find only odd neighbours. Then $d$ scans $e$: both even, both in the tree of $s$. Their tree paths meet at $b$, so the blossom is $b,c,d,e,f$ with base $b$.

Shrink it to a vertex $B$. In $L/B$ the matching has three edges: $a$–$B$ (inherited from $b$), $p$–$q$ and $u$–$w$. $B$ is even, with parent $a$, and it is scanned again. Its neighbours are $a$ (odd) and $p$, which $B$ inherits from $c$. $p$ is even in the tree of $t$. Two trees meet, and the path is $s,a,B,p,q,t$.

To lift it, look at the edge by which the path leaves $B$ without using $B$'s matched edge: here $B$–$p$, which came from $c$–$p$. The path must enter the blossom at $c$ and travel to the base $b$ along the side that starts with $c$'s matched edge $c$–$d$. That side is $c,d,e,f,b$, four edges, an even number. The other side, $c$–$b$ directly, would start with an unmatched edge and break the alternation. Then $b$'s matched edge to $a$ continues the path out of the blossom.

def flip(M, path):
    return M ^ {edge(x, y) for x, y in zip(path, path[1:])}

def augments(G, M, path):
    """A simple path between exposed vertices whose flip is a larger matching."""
    ends_free = not any(path[0] in e or path[-1] in e for e in M)
    new = flip(M, path)
    return (len(set(path)) == len(path) and ends_free
            and is_matching(G, new) and len(new) == len(M) + 1)

blossom = ["b", "c", "d", "e", "f"]
assert all(edge(x, y) in {edge(u, v) for u in L for v in L[u]}
           for x, y in zip(blossom, blossom[1:] + blossom[:1]))
assert sum(edge(x, y) in M for x, y in zip(blossom, blossom[1:] + blossom[:1])) == 2

shrink = lambda v: "B" if v in blossom else v          # L/B, as a set of edges
LB_edges = {edge(shrink(x), shrink(y)) for x in L for y in L[x]} - {edge("B", "B")}
LB = {}
for x, y in map(tuple, LB_edges):
    LB.setdefault(x, set()).add(y)
    LB.setdefault(y, set()).add(x)
MB = {edge(shrink(x), shrink(y)) for x, y in map(tuple, M)} - {edge("B", "B")}
assert sorted(LB["B"]) == ["a", "p"] and len(LB) == 8
assert augments(LB, MB, ["s", "a", "B", "p", "q", "t"])

lifted = ["s", "a", "b", "f", "e", "d", "c", "p", "q", "t"]
assert augments(L, M, lifted)
assert not augments(L, M, ["s", "a", "b", "c", "p", "q", "t"])   # the short side
assert len(flip(M, lifted)) == 6                                 # everyone has a room

Why shrinking is safe

Say the search has found a blossom $B$ with base $\beta$ in the graph $G$ with matching $M$, and $G^{\prime }=G/B$, $M^{\prime }=M/B$ are the shrunk graph and matching.

Lemma (lifting). If $P^{\prime }$ is an augmenting path for $M^{\prime }$ in $G^{\prime }$, then $G$ has an augmenting path for $M$, obtained by replacing the shrunk vertex $b$ by a path through $B$.

Proof. If $b$ is not on $P^{\prime }$, $P^{\prime }$ is augmenting in $G$ as it stands: its edges and their matched status are unchanged. Otherwise, write the cycle as $\beta =c_0,c_1,\dots ,c_{2k}$ with $c_1{c}_2,c_3{c}_4,\dots ,c_{2k-1}{c}_{2k}$ matched. The vertex $b$ has at most one matched edge in $G^{\prime }$, the base's old edge. So among its edges on $P^{\prime }$, one is unmatched, $u$–$b$, and the other, if $b$ is not an end of $P^{\prime }$, is matched and leads to the base's partner. Choose a $c_i$ adjacent to $u$ in $G$. If $i=0$, use $\beta$ alone. If $i$ is odd, go $c_i,c_{i+1},\dots ,c_{2k},\beta$. If $i>0$ is even, go $c_i,c_{i-1},\dots ,c_1,\beta$. Either way the segment has even length, starts at $c_i$ with a matched edge and arrives at $\beta$ on an unmatched one. So $u$–$c_i$ (unmatched), the segment, and then $\beta$'s matched edge out of $B$ alternate. If instead $b$ was an end of $P^{\prime }$, then $\beta$ is exposed and the segment ends the path there. The segment stays inside $B$ and the rest of $P^{\prime }$ outside it, so the path is simple. $◻$

The converse (an augmenting path in $G$ gives one in $G^{\prime }$) also holds for a blossom found by the search. Sketch, not proved here: flipping the stem, which has even length, keeps $|M|$ and makes $\beta$ exposed. Then take an augmenting path in $G$, start at an end that is not $\beta$ and stop at the first vertex of $B$: shrunk, that prefix ends at the now exposed $b$. The algorithm below does not need the converse, because it proves that its final matching is maximum in another way: with a certificate.

The certificate: Tutte–Berge

Suppose $c$ and $p$ fall out and no longer agree to share. The algorithm stops at five rooms. Why can nobody do better?

Remove a set $U$ of vertices and count the connected pieces of $G-U$ that have an odd number of vertices: $odd(G-U)$. Inside an odd piece the vertices can't all be matched to each other, so each odd piece has a vertex that is exposed or matched to a vertex of $U$, and $U$ can absorb at most $|U|$ of them.

The easy half, proved. For every matching $M$ and every $U$, at least $odd(G-U)-|U|$ vertices are exposed, so $|M|\le \frac{1}{2}(|V|-odd(G-U)+|U|)$. This is the analogue of weak duality in Network Flow and Matchings: every $U$ is an upper bound, and a matching that meets one is maximum.

The other half, witnessed by the algorithm. When a search from all exposed vertices ends with no path, let $U$ be its odd vertices. They are original vertices, since shrunk vertices are always even. When the search stops, every edge from an even vertex has been scanned, so every neighbour of an even vertex is odd or lies inside the same shrunk vertex. So each even vertex, expanded back into the original vertices it stands for, is a whole connected piece of $G-U$, and it is odd: a blossom is an odd cycle of pieces that are each odd. The unlabelled vertices are matched to each other and have no even neighbours, so their pieces have even size. In each tree every odd vertex has exactly one even child, and every even vertex except the root is the child of one odd vertex, so there are $|U|+(\text{number of roots})$ even vertices. Therefore $odd(G-U)=|U|+(\text{exposed vertices})$, and the bound becomes $\frac{1}{2}(|V|-\text{exposed})=|M|$. The matching meets the bound, so it is maximum. With the lifting lemma, that proves the algorithm correct, and the minimum in the formula is attained.

L2 = {x: set(ys) for x, ys in L.items()}      # c and p no longer share
L2["c"].discard("p")
L2["p"].discard("c")

def odd_pieces(G, U):
    seen, odd = set(U), 0
    for v in G:
        if v not in seen:
            stack, size = [v], 0
            seen.add(v)
            while stack:
                x = stack.pop()
                size += 1
                for y in G[x] - seen:
                    seen.add(y)
                    stack.append(y)
            odd += size % 2
    return odd

def bound(G, U):
    return (len(G) + len(U) - odd_pieces(G, U)) // 2

U = {"a", "q", "u"}
assert odd_pieces(L2, U) == 5 and bound(L2, U) == 5 == maximum(L2)
subsets = product([False, True], repeat=12)
assert min(bound(L2, {v for v, inside in zip(names, pick) if inside})
           for pick in subsets) == 5                   # no set proves less

The notice for the two students left over writes itself: "Without $a$, $q$ and $u$ the rest split into five groups of odd size. Each group has someone who must room with $a$, $q$ or $u$ or not at all, so at least two students are left without a room."

Tutte's theorem (1947) is the case of a perfect matching: $G$ has one if and only if $odd(G-U)\le |U|$ for every $U$. It follows from the formula with $\nu (G)=|V|/2$.

Cost

Count in the word-RAM model with the graph stored as adjacency lists and per-vertex arrays for labels, parents and partners. A scan is one look at a neighbour of a vertex taken from the queue.

Between two shrinks a search labels each vertex at most once, and each shrink removes at least two vertices (a blossom has at least three), so there are at most $V/2$ shrinks per search. Each contraction can require $O(V+E)$ work to rebuild the shrunk graph and rescan what changed, and between two contractions the search scans each vertex's neighbours at most once, another $O(V+E)$. With $O(V)$ contractions in one search, one search therefore costs $O(V·(V+E))$ in the worst case. Each search except the last adds an edge to the matching, so there are at most $\nu +1\le V/2+1$ searches. That gives a worst-case total of

$$O(V^2(V+E)),$$

which is $O(V^{2}E)$ when no vertex is isolated. Careful implementations reach $O(V^3)$ by shrinking without rebuilding (Gabow, 1976). Micali and Vazirani (1980) reach $O(E\sqrt{V})$, the Hopcroft–Karp bound for bipartite matching. A complete and correct proof of their algorithm was finally published in journal form in 2024 (Vazirani, Math. Oper. Res.). Both are cited here, not proved.

Maximum-weight matching in general graphs is also solvable in polynomial time (Edmonds, 1965, with blossoms and LP duality), but it is outside this module.

Measure the claim

Here are the searches on random graphs where each of $n$ vertices picks 3 random others (seed $451+n$), starting from the empty matching and scanning in increasing order:

Each graph has a perfect matching, and there are exactly $\nu +1$ searches. Scans stay far below the bound because early searches find an exposed neighbour in a step or two, and the number of blossoms jumps with the instance. These are measurements on these instances, not guarantees; the lab builds a family where a single search shrinks about $V/4$ blossoms.

A problem that looks different

A build farm has two identical machines and a batch of one-minute jobs. Some jobs must finish before others start. In each minute, a machine runs one job, or sits idle. Two jobs can share a minute only if neither has to come before the other. What is the fewest number of minutes, and why might that number depend on how many jobs can be run two at a time? Nothing here has two sides. The lab's last problem is a different one.

Practise

In the lab you flip augmenting paths and reject paths that only look like them; predict, then trace, the forest, the blossom and the shrunk graph on a new instance; write the whole blossom algorithm with its certificate and test it against brute force and against the search from module 11; count the scans on graphs where the number of blossoms per search grows with the graph; and solve a pairing problem that doesn't say what it is.

Recap

You can now: prove Berge's theorem; explain why the layered search of bipartite matching misses augmenting paths through odd cycles; find, shrink and lift a blossom; and read a Tutte–Berge set $U$ off the final forest, as a certificate that anyone can check.

Invariant: the search keeps an alternating forest whose roots are exactly the exposed vertices, and every shrunk vertex is even and stands for an odd set of original vertices. When no path is left, the odd vertices $U$ satisfy $|M|=\frac{1}{2}(|V|+|U|-odd(G-U))$.

Complexity achieved: at most $\nu +1$ searches of $O(V(V+E))$ each: $O(V^2(V+E))$ worst case, polynomial, against trying every subset of edges. Faster: $O(V^3)$ (Gabow) and $O(E\sqrt{V})$ (Micali–Vazirani), cited.

Failure mode: treating the graph as bipartite. The search keeps a vertex's first label, and a vertex that should be even through an odd cycle stays odd, so the search stops at a matching that is not maximum and reports nothing wrong.

In real software: NetworkX's max_weight_matching(G, maxcardinality=True) computes a maximum matching with Edmonds' blossom method, and its documentation states $O(V^3)$ time. The Boost Graph Library's checked_edmonds_maximum_cardinality_matching runs Edmonds' algorithm and then verifies the result by checking the Tutte–Berge equality with $U$ taken from the search's odd labels.

Retrieval (Network Flow and Matchings): in bipartite matching, the certificate that no larger matching exists was a minimum cut. How does a minimum cut in the unit network give a set of at most $\nu$ people and jobs that touches every allowed pair?

Check yourself

1. Why is the set of odd vertices of the final forest a Tutte–Berge set that meets the bound? Count the even vertices.
2. Remove the edge $w$–$a$ from $L$ and keep the same five rooms. Does the layered search still fail from both $s$ and $t$? What was that edge doing?
3. On a bipartite graph, compare the blossom algorithm with the search from Network Flow and Matchings. What does the blossom algorithm do there that the other does not?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.