Graph Matching and Hall's Marriage Theorem

Core Idea

A matching is a set of edges with no common vertices. A perfect matching covers all vertices. Hall's Marriage Theorem: a bipartite graph G = (X ∪ Y, E) has a matching covering all vertices in X if and only if for every subset S ⊆ X, |N(S)| ≥ |S|, where N(S) is the neighborhood of S.

Explainer

From your study of bipartite graphs, you know that a bipartite graph separates its vertices into two independent sets X and Y, with edges only running between the sets — never within them. Imagine X represents a set of job applicants and Y represents job openings, with an edge meaning "this applicant is qualified for this job." A matching is an assignment of applicants to jobs where no two applicants share a job and no applicant holds multiple jobs — formally, a set of edges with no repeated vertices. A perfect matching from X to Y assigns every applicant in X to a distinct job.

The obvious question is: when does such an assignment exist? Hall's Marriage Theorem gives a clean, complete answer. The condition is intuitively natural: for every group S of applicants, there must be at least |S| distinct jobs they are collectively qualified for. If five applicants are all only qualified for the same two jobs, no assignment can work — three will be left out. Formally, for every subset S ⊆ X, the neighborhood N(S) (all vertices in Y adjacent to at least one vertex in S) must satisfy |N(S)| ≥ |S|. This is called Hall's condition.

What makes the theorem remarkable is that it is both necessary *and* sufficient. It's obvious that Hall's condition is necessary (if some S violates it, you can't match those vertices). The deep part is sufficiency: if Hall's condition holds for *every* possible subset S, then a perfect matching is guaranteed to exist. You don't need to construct the matching explicitly to know it exists — the condition alone certifies it. The proof proceeds by strong induction on |X|, considering whether the graph is "tight" (some S achieves |N(S)| = |S|) or "loose" everywhere.

Hall's theorem is a template for a broader class of existence results. Whenever you want to show that a combinatorial assignment exists without constructing it explicitly, you look for a condition analogous to Hall's that eliminates the obvious obstructions and then proves no others can occur. This same logic underlies network flow algorithms and Latin square completions. In practice, if you can verify Hall's condition algorithmically, you can also *find* a maximum matching using augmenting path algorithms — the theorem tells you what to look for, and the algorithm finds it.