Matchings: Hall’s theorem, König’s theorem and stable marriage

A matching in a graph is a set of edges no two of which share a vertex. Matchings model pairing problems everywhere: assigning workers to jobs they can do, students to schools, organ donors to compatible recipients, kidney exchanges, and processors to tasks. The questions are how large a matching can be, when everyone can be matched, how to find a best matching quickly, and, when people have preferences, how to match them so that the result is stable. This lesson answers all four for bipartite graphs and indicates what changes in general.

Maximum matchings and augmenting paths

A vertex is covered, or saturated, by a matching \(M\) if it is an endpoint of an edge of \(M\). A matching is perfect if it covers every vertex, maximum if no matching has more edges, and maximal if no edge can be added to it. Maximal does not imply maximum: in the path \(a\)–\(b\)–\(c\)–\(d\), the single edge \(bc\) is maximal, but \(\{ab, cd\}\) is larger. The size of a maximum matching is written \(\nu(G)\).

An \(M\)-alternating path alternates between edges not in \(M\) and edges in \(M\). It is \(M\)-augmenting if it starts and ends at vertices not covered by \(M\). Such a path has one more non-matching edge than matching edge, so swapping them, replacing \(M\) by the symmetric difference \(M \triangle P\), produces a matching with one more edge.

Theorem (Berge, 1957). A matching \(M\) is maximum if and only if there is no \(M\)-augmenting path.

Proof. If an augmenting path exists, flipping it enlarges \(M\). Conversely, suppose \(M\) is not maximum and \(M'\) is larger. In the symmetric difference \(M \triangle M'\), every vertex has degree at most 2, one edge from each matching, so its components are paths and even cycles whose edges alternate between \(M\) and \(M'\). Cycles have equally many edges from each. Since \(|M'| > |M|\), some path component has more edges of \(M'\) than of \(M\); it starts and ends with edges of \(M'\), and its ends are not covered by \(M\), since otherwise the path would continue. That path is \(M\)-augmenting.

Berge's theorem gives an algorithm: start with any matching and repeatedly search for an augmenting path. In a bipartite graph with sides \(X\) and \(Y\), a breadth-first search from all uncovered vertices of \(X\), following non-matching edges from \(X\) to \(Y\) and matching edges back, finds one in time proportional to the number of edges, so a maximum matching takes \(O(VE)\) time. John Hopcroft and Richard Karp showed in 1973 how to augment along many shortest paths at once, improving this to \(O(E\sqrt V)\).

Hall's marriage theorem

Let \(G\) be bipartite with sides \(X\) and \(Y\). For \(S \subseteq X\), let \(N(S)\) be the set of vertices of \(Y\) adjacent to some vertex of \(S\). If a matching covers all of \(X\), then the vertices of \(S\) are matched to \(|S|\) distinct vertices of \(N(S)\), so \(|N(S)| \ge |S|\). Philip Hall proved in 1935 that this obvious necessary condition is also sufficient.

Theorem (Hall). A bipartite graph with sides \(X\) and \(Y\) has a matching covering \(X\) if and only if \(|N(S)| \ge |S|\) for every \(S \subseteq X\).

Proof of sufficiency. Induct on \(|X|\); the case \(|X| = 1\) is clear. Case 1: every nonempty proper subset \(S\) of \(X\) satisfies \(|N(S)| \ge |S| + 1\). Match any \(x \in X\) to any neighbor \(y\), and delete both. In the remaining graph each nonempty \(S \subseteq X - x\) has lost at most one neighbor, so it still has at least \(|S|\) neighbors, and by induction the rest of \(X\) can be matched. Case 2: some nonempty proper subset \(S_0\) has \(|N(S_0)| = |S_0|\). The subgraph on \(S_0 \cup N(S_0)\) satisfies Hall's condition, since neighborhoods of subsets of \(S_0\) lie inside \(N(S_0)\), so by induction \(S_0\) can be matched into \(N(S_0)\). In the subgraph on \((X - S_0) \cup (Y - N(S_0))\), take \(T \subseteq X - S_0\). Then \(N(T \cup S_0) = N_{\text{rest}}(T) \cup N(S_0)\), where \(N_{\text{rest}}(T)\) is the set of neighbors of \(T\) outside \(N(S_0)\), and by Hall's condition \(|N_{\text{rest}}(T)| + |S_0| \ge |T| + |S_0|\). So the second subgraph also satisfies Hall's condition, and by induction \(X - S_0\) can be matched into \(Y - N(S_0)\). The two matchings together cover \(X\).

Hall's theorem is a statement about systems of distinct representatives. Given a family of sets \(A_1, \ldots, A_m\), one can choose distinct elements \(a_i \in A_i\) if and only if every \(k\) of the sets together contain at least \(k\) elements. Applications include completing Latin squares (Marshall Hall, 1945, showed that every \(r \times n\) Latin rectangle extends to a Latin square) and the Birkhoff–von Neumann theorem that every doubly stochastic matrix is an average of permutation matrices.

Corollary. Every \(k\)-regular bipartite graph with \(k \ge 1\) has a perfect matching. Proof: for \(S \subseteq X\), the \(k|S|\) edges leaving \(S\) all land in \(N(S)\), where each vertex receives at most \(k\) edges, so \(k|N(S)| \ge k|S|\). Hall's condition holds; and since \(k|X| = k|Y|\), the sides are equal and the matching is perfect. Removing it leaves a \((k - 1)\)-regular bipartite graph, so the edges split into \(k\) perfect matchings. This proves König's 1916 theorem that a regular bipartite graph has edge chromatic number equal to its degree; with a little extra work, every bipartite graph has \(\chi' = \Delta\).

König's theorem

A vertex cover is a set of vertices touching every edge. Each edge of a matching needs its own cover vertex, so every cover is at least as large as every matching: \(\nu(G) \le \tau(G)\), where \(\tau\) is the smallest size of a vertex cover. In general the inequality can be strict; a triangle has \(\nu = 1\) and \(\tau = 2\). For bipartite graphs it is an equality.

Theorem (König, 1931; Egerváry, 1931). In a bipartite graph, the maximum size of a matching equals the minimum size of a vertex cover.

Proof. Let \(M\) be a maximum matching, \(U\) the set of uncovered vertices in \(X\), and \(Z\) the set of vertices reachable from \(U\) by \(M\)-alternating paths. Put \(C = (X \setminus Z) \cup (Y \cap Z)\). First, \(C\) is a cover: an edge \(xy\) with \(x \in X \cap Z\) puts \(y\) in \(Z\), because an alternating path reaching \(x\) arrives along a matching edge (or starts at \(x\)), and can continue along \(xy\) if \(xy \notin M\); if \(xy \in M\), then \(x\) was reached from \(y\), so \(y \in Z\) again. Second, every vertex of \(C\) is covered by \(M\) and no edge of \(M\) has both ends in \(C\): each \(y \in Y \cap Z\) is matched, since otherwise the alternating path to it would be augmenting, contradicting Berge; its partner is in \(X \cap Z\), outside \(C\). Each \(x \in X \setminus Z\) is matched, since uncovered vertices of \(X\) are in \(U \subseteq Z\), and its partner is in \(Y \setminus Z\), outside \(C\). So \(|C| = |M|\).

Hall's theorem follows from König's: if no matching covers \(X\), there is a cover \(C\) with \(|C| < |X|\); then \(S = X \setminus C\) has all its neighbors in \(Y \cap C\), so \(|N(S)| \le |C| - |X \cap C| < |X| - |X \cap C| = |S|\). The proof above is also an algorithm for finding a Hall violator, which the program uses. Lesson 11 derives König's theorem once more from the max-flow min-cut theorem. Its weighted version leads to the Hungarian algorithm of Harold Kuhn (1955), named in honor of König and Egerváry, which finds a minimum-cost assignment of \(n\) workers to \(n\) jobs in polynomial time.

General graphs. Odd cycles make non-bipartite graphs harder, because an alternating search can loop back on itself. William Tutte characterized graphs with perfect matchings in 1947: \(G\) has one if and only if, for every vertex set \(S\), removing \(S\) leaves at most \(|S|\) components with an odd number of vertices. Jack Edmonds gave the blossom algorithm in 1965, which shrinks odd cycles and finds maximum matchings in polynomial time. His paper, Paths, Trees, and Flowers, also argued that polynomial time is the right notion of an efficient algorithm, a founding idea of complexity theory.

Stable marriage

Suppose \(n\) applicants and \(n\) positions each rank all members of the other side. A perfect matching is unstable if some applicant and position, not matched to each other, both prefer each other to their assigned partners: such a pair would break away. A matching with no such blocking pair is stable. David Gale and Lloyd Shapley showed in 1962 that a stable matching always exists, by an algorithm now called deferred acceptance.

The algorithm. Each unmatched applicant proposes to the highest-ranked position that has not yet rejected them. Each position holds its most preferred proposal so far and rejects the rest, including any proposal it was holding if a better one arrives. Repeat until nobody is unmatched.

Theorem (Gale–Shapley). Deferred acceptance terminates after at most \(n^2\) proposals with a stable perfect matching.

Proof. Each applicant proposes to each position at most once, so there are at most \(n^2\) proposals. A position, once it receives a proposal, always holds one, and only ever trades up. If some applicant ended unmatched, they would have been rejected by all \(n\) positions, each of which then holds a proposal, from \(n\) distinct applicants other than this one, which is impossible. So the result is perfect. For stability, suppose applicant \(a\) prefers position \(p\) to their final partner. Then \(a\) proposed to \(p\) earlier and was rejected, at that time or later, in favor of someone \(p\) preferred; since \(p\) only trades up, \(p\) prefers its final partner to \(a\). So \((a, p)\) is not a blocking pair.

More is true: the stable matching found is the best possible for every applicant among all stable matchings, and the worst possible for every position. Swapping who proposes swaps the advantage. Variants of the algorithm run the National Resident Matching Program in the United States, the Canadian Resident Matching Service, school choice in New York and Boston, and kidney exchange programs. Lloyd Shapley and Alvin Roth received the 2012 Nobel Memorial Prize in Economic Sciences for the theory of stable allocations and its applications; Gale had died in 2008.

import random

def max_matching(left, adj):
    match_r = {}
    def try_augment(u, seen):
        for v in adj[u]:
            if v in seen:
                continue
            seen.add(v)
            if v not in match_r or try_augment(match_r[v], seen):
                match_r[v] = u
                return True
        return False
    for u in left:
        try_augment(u, set())
    return {u: v for v, u in match_r.items()}

def konig_cover(left, adj, match):
    """Vertex cover of size |match| and a Hall violator if one exists."""
    partner_of_right = {v: u for u, v in match.items()}
    frontier = [u for u in left if u not in match]
    Z = set(("L", u) for u in frontier)
    while frontier:
        nxt = []
        for u in frontier:
            for v in adj[u]:
                if ("R", v) not in Z:
                    Z.add(("R", v))
                    w = partner_of_right.get(v)
                    if w is not None and ("L", w) not in Z:
                        Z.add(("L", w)); nxt.append(w)
        frontier = nxt
    cover = [("L", u) for u in left if ("L", u) not in Z] + sorted(x for x in Z if x[0] == "R")
    violator = sorted(u for u in left if ("L", u) in Z)
    return cover, violator

workers = ["a", "b", "c", "d", "e"]
can_do = {"a": [1, 2], "b": [2], "c": [2, 3], "d": [2, 3], "e": [3, 4, 5]}
M = max_matching(workers, can_do)
cover, S = konig_cover(workers, can_do, M)
NS = sorted({v for u in S for v in can_do[u]})
print("maximum matching:", M, " size", len(M))
print("minimum vertex cover:", cover, " size", len(cover))
print("Hall violator S =", S, " N(S) =", NS)

from itertools import combinations
random.seed(1935)
n = 7
agree = True
for trial in range(300):
    adj = {i: [j for j in range(n) if random.random() < 0.3] for i in range(n)}
    hall = all(len({v for u in S for v in adj[u]}) >= len(S) for r in range(1, n + 1) for S in combinations(range(n), r))
    if hall != (len(max_matching(range(n), adj)) == n):
        agree = False
print("Hall's condition and a perfect matching agree on 300 random bipartite graphs:", agree)

def gale_shapley(prop_pref, recv_pref):
    rank = {r: {p: i for i, p in enumerate(lst)} for r, lst in recv_pref.items()}
    nxt = {p: 0 for p in prop_pref}
    held = {}
    free = list(prop_pref)
    proposals = 0
    while free:
        p = free.pop()
        r = prop_pref[p][nxt[p]]; nxt[p] += 1; proposals += 1
        if r not in held:
            held[r] = p
        elif rank[r][p] < rank[r][held[r]]:
            free.append(held[r]); held[r] = p
        else:
            free.append(p)
    return {p: r for r, p in held.items()}, proposals

def blocking_pairs(match, prop_pref, recv_pref):
    partner = {r: p for p, r in match.items()}
    bad = []
    for p, prefs in prop_pref.items():
        for r in prefs[:prefs.index(match[p])]:
            if recv_pref[r].index(p) < recv_pref[r].index(partner[r]):
                bad.append((p, r))
    return bad

applicants = {"Ana": ["X", "Y", "Z"], "Ben": ["Y", "X", "Z"], "Cai": ["X", "Y", "Z"]}
positions = {"X": ["Ben", "Ana", "Cai"], "Y": ["Ana", "Ben", "Cai"], "Z": ["Ana", "Ben", "Cai"]}
m1, n1 = gale_shapley(applicants, positions)
m2, n2 = gale_shapley(positions, applicants)
print("applicants propose:", dict(sorted(m1.items())), "proposals", n1, "blocking pairs", blocking_pairs(m1, applicants, positions))
print("positions propose: ", dict(sorted({v: k for k, v in m2.items()}.items())), "proposals", n2)

random.seed(2012)
N = 200
A = {i: random.sample(range(N), N) for i in range(N)}
B = {j: random.sample(range(N), N) for j in range(N)}
m, props = gale_shapley(A, B)
avg = sum(A[i].index(m[i]) + 1 for i in range(N)) / N
print(f"random instance, n={N}: proposals {props}, stable: {not blocking_pairs(m, A, B)}, average rank of applicants' partners {avg:.2f}")

maximum matching: {'a': 1, 'b': 2, 'c': 3, 'e': 4}  size 4
minimum vertex cover: [('L', 'a'), ('L', 'e'), ('R', 2), ('R', 3)]  size 4
Hall violator S = ['b', 'c', 'd']  N(S) = [2, 3]
Hall's condition and a perfect matching agree on 300 random bipartite graphs: True
applicants propose: {'Ana': 'X', 'Ben': 'Y', 'Cai': 'Z'} proposals 5 blocking pairs []
positions propose:  {'Ana': 'Y', 'Ben': 'X', 'Cai': 'Z'} proposals 5
random instance, n=200: proposals 917, stable: True, average rank of applicants' partners 4.58

The worker example has a maximum matching of size 4, a vertex cover of the same size certifying optimality, and the Hall violator \(\{b, c, d\}\) with only jobs 2 and 3 between them. On 300 random bipartite graphs, checking Hall’s condition over all subsets and searching for a perfect matching always give the same verdict. In the small stable marriage example, the two directions of proposal give different stable matchings, each better for the proposing side. For 200 random applicants, deferred acceptance needs far fewer than the maximum \(n^2 = 40{,}000\) proposals, and applicants get on average a partner ranked about \(\ln n\) from the top, as Donald Knuth's analysis predicts.