One bottleneck and nothing else

Five posts are open and five people have applied, each qualified for some of them. Can every post be filled by a different person? The question has an obvious way to fail — three people between them qualified for only two posts — and the content of Hall’s theorem is that this is the only way.

That is a strong statement, and the reason it is worth stating is that failure is usually harder to certify than success. A complete assignment can be exhibited; the claim that none exists is a claim about every one of the assignments that were not tried. Hall’s theorem replaces that claim with a set of people to point at.

The condition, and why it is obviously necessary #

Draw the situation as a graph: a dot for each applicant on one side, a dot for each post on the other, and an edge whenever that applicant could take that post. A matching is a set of edges no two of which share a dot; a matching is complete on the left when every applicant is in it.

If a complete matching exists, then for any set $S$ of applicants, the posts they are matched to are distinct and all lie among the posts $S$ can take. So

$$|N(S)| \ge |S| \quad \text{for every set } S,$$

where $N(S)$ is the set of posts adjacent to at least one member of $S$. That is Hall’s condition, and this paragraph is the whole proof of its necessity. It is the pigeonhole principle wearing different clothes: $|S|$ people needing distinct posts from a pool of $|N(S)|$ cannot manage it when the pool is smaller.

The surprise is the converse. Hall’s theorem says that if the condition holds for every one of the $2^n - 1$ non-empty sets, a complete matching exists. Nothing in the condition constructs a matching; it merely rules out the one visible way of failing, and the theorem says that ruling that out is enough.

What failure looks like #

Every figure in this essay computes two quantities by routes that share no code. A largest matching is found by looking for improvements: given a partial matching, an augmenting path starts at an unmatched applicant, alternates between unused and used edges, and ends at an unmatched post; flipping the used and unused edges along it makes the matching one larger. A matching with no augmenting path is as large as possible — that is Berge’s lemma, and it is what turns “search for improvements” into a proof of maximality rather than a heuristic.

The other route is the subset scan: look at all $2^n - 1$ sets of applicants, compute the neighbours of each, and record the worst overshoot. The two numbers are then required to agree, and the reason they must is the deficiency form of the theorem below.

The deficiency form, which says how much is missing #

Hall’s theorem in its sharp form does not merely say matching or no matching. Define the deficiency of a set $S$ as $|S| - |N(S)|$, and let $d$ be the largest deficiency over all sets. Then the largest matching has size

$$n - d,$$

where $n$ is the number of applicants. Hall’s theorem is the case $d = 0$.

The inequality in one direction is the counting argument again: a matching must leave at least $d$ applicants out. The other direction is the theorem, and here is a proof of it that costs one paragraph, by reducing to the case $d = 0$.

Add $d$ new posts and join every applicant to all of them. Any set $S$ now has $|N(S)| + d \ge |S|$ neighbours, so Hall’s condition holds in the enlarged graph and a complete matching exists there by the basic theorem. Delete the new posts; at most $d$ applicants lose their partner, so at least $n - d$ remain matched. That is the bound, and the trick — enlarge until the hypothesis holds, then subtract — is worth remembering, because it converts every counting theorem of this shape into its own sharp form.

Why the condition is sufficient #

The standard proof is by induction on the number of applicants, and it splits into two cases according to whether the condition holds with room to spare.

Suppose every non-empty set $S$ of applicants with $S$ not the whole side satisfies $|N(S)| \ge |S| + 1$ — the condition holds strictly on every proper subset. Then match any one applicant to any post they can take, and delete both. Every remaining set has lost at most one neighbour, so it still satisfies $|N(S)| \ge |S|$; the smaller graph satisfies the condition, and induction finishes it.

Otherwise some proper non-empty set $T$ is tight: $|N(T)| = |T|$. Split the problem. Inside, $T$ and $N(T)$ satisfy the condition, so induction matches $T$ completely into $N(T)$, using up all of $N(T)$. Outside, consider the applicants not in $T$ with the posts of $N(T)$ removed. Any set $S$ of them satisfies Hall’s condition in the reduced graph, because $S \cup T$ satisfies it in the original: $|N(S \cup T)| \ge |S| + |T|$ and $N(T)$ contributes exactly $|T|$ of those, so $S$ has at least $|S|$ neighbours outside $N(T)$. Induction again, and the two matchings are disjoint by construction.

That is the whole argument, and its shape is worth noticing: the tight sets are the only obstacle, and where one exists it is not an obstruction but a seam — a place where the problem falls into two independent problems.

Every regular graph has one #

One corollary is used far more often than the theorem it comes from, and its proof is arithmetic rather than induction.

Suppose every vertex has exactly $k$ edges. Take any set $S$ of applicants; the edges leaving $S$ number $k|S|$, and every one of them lands in $N(S)$, where at most $k|N(S)|$ edges can arrive. So $k|S| \le k|N(S)|$, and the condition holds. Hall gives a complete matching; removing it leaves a graph in which every vertex has $k-1$ edges; repeat. A $k$-regular bipartite graph therefore splits into exactly $k$ complete matchings — which is the statement that its edges can be coloured in $k$ colours with no two edges of a colour meeting, and the figure above does the splitting rather than asserting it.

This corollary is the engine behind two results elsewhere on this site. It is why a doubly stochastic table of shares is a lottery over whole assignments: the support of such a table satisfies Hall’s condition by the same counting, so a whole assignment can always be taken out of it. And it is why a partial Latin square of the right shape can always be completed.

A Latin rectangle is a $k \times n$ array with $n$ symbols, each appearing once in each row and at most once in each column. Can it be extended by another row? Form the bipartite graph with columns on one side and symbols on the other, joined when that symbol is still missing from that column. Each column is missing exactly $n - k$ symbols and each symbol is missing from exactly $n - k$ columns, so the graph is regular; a complete matching exists; that matching is the new row. So every Latin rectangle extends, one row at a time, to a full Latin square — a statement about completion, proved without ever completing anything.

The same theorem, five other names #

Hall’s theorem is a member of a family whose members are equivalent to one another, and the equivalences are short. It is worth knowing them, because a problem often arrives in one dress and is easiest in another.

König’s theorem: in a bipartite graph, the largest matching and the smallest set of vertices touching every edge have the same size. Menger’s theorem: the largest number of disjoint paths between two vertices equals the smallest number of vertices whose removal separates them. Dilworth’s theorem: in a partial order, the fewest chains needed to cover everything equals the largest set of mutually incomparable elements. And the max-flow min-cut theorem, of which the others are special cases, is the same duality between a maximisation and a minimisation that a linear program exhibits.

Each of these has the shape the best that can be done equals the worst obstruction there is, and each is provable from Hall in a few lines. That is the standing reason to care about a min–max theorem: it converts an existence question, whose negative answer is a statement about everything, into a certificate that can be checked by inspection. A referee who doubts that a matching is largest can be handed the tight set, count it, count its neighbours, and be finished.

Where it fails, and what it needs #

Three conditions are doing real work, and each has a counterexample when dropped.

Bipartite matters. In a general graph the analogue is false; the odd cycles get in the way, and the correct statement is Tutte’s theorem, whose condition is about the number of odd components left after deleting a set of vertices. A triangle with a pendant edge has no perfect matching, and nothing that looks like Hall’s condition sees it.

Finiteness matters, but less than it looks. For infinite graphs the theorem holds when every vertex on the left has finitely many neighbours — a compactness argument stitches together the finite cases, exactly the argument that an infinite tree with finite branching has an infinite path. Without the finite-degree hypothesis it can fail.

Checking the condition is not free. There are $2^n - 1$ sets, and the theorem says nothing about finding the bad one quickly. What makes the result usable is that the augmenting-path search produces a tight set as a by-product when it stops: the vertices reachable by alternating paths from an unmatched applicant form a set with too few neighbours. So the certificate comes out of the search, and nobody ever enumerates the subsets — though the figures here do, precisely so that the two computations are independent.

Where it came from, and the name it was given #

Philip Hall proved the theorem in 1935, in a paper about something else. He was working on subgroups and cosets, and needed to know when a family of sets has a system of distinct representatives — one element chosen from each set, all choices different. That is the same question: make a graph with the sets on one side, their elements on the other, and an edge for membership.

The set-theoretic phrasing is the one worth carrying, because it applies where no graph is in sight. Given finitely many finite sets $A_1, \dots, A_n$, distinct representatives can be chosen exactly when every collection of $k$ of the sets has at least $k$ elements in its union. Committees needing distinct chairs, terms needing distinct pivots, cosets needing distinct representatives: the same theorem each time.

The marriage phrasing — $n$ women, $n$ men, each woman willing to marry some of the men — came later, from expositions in the 1940s and 1950s, and it has outlasted its usefulness. It carries an irrelevant symmetry suggestion, since the theorem is one-sided: it matches the left side completely into the right and says nothing about whether the right side is used up. It also invites the false intuition that both sides must be the same size, when the natural statement has a large right side and a small left one. The graph version and the representatives version are both cleaner, and the deficiency version is cleaner still.

Two independent rediscoveries are worth recording, because they show how basic the statement is. König had proved the equivalent min–max theorem for bipartite graphs in 1931, and Egerváry generalised it to weights the same year; the max-flow min-cut theorem of the 1950s subsumes all of it. A statement proved four times from four directions in twenty-five years is usually a statement about something structural rather than about the objects in its first proof.

What the pictures cannot show #

The graphs drawn here have four or five vertices a side, which is small enough that a reader can see the answer, and that is a real limitation: the interesting cases are the ones where the eye cannot find either the matching or the tight set. Nothing in a small picture conveys that the subset scan is exponential while the augmenting search is not.

Nor can a picture show what the theorem’s converse direction costs. The necessity of Hall’s condition is visible — a set with too few neighbours plainly cannot be matched — and the sufficiency is the whole theorem, and there is no drawing of it. The best a figure can do is what the deficiency table does: show the two numbers agreeing on several graphs, which is evidence and not proof.

And a static figure cannot show the augmenting path doing its work, since the mechanism is a sequence of flips. That is drawn here only in its result, the larger matching, and the reader has to take the intermediate steps on trust or redraw them.

The ladder from here #

Below: the pigeonhole principle, which is the counting fact Hall’s condition generalises, and stable matching, which asks a different question about the same bipartite picture — not whether everyone can be matched but whether anyone would want to defect. Sideways: Latin squares, where the completion argument above is the standard tool, and linear programming duality, which is the general shape this theorem is a corner of. Above: the assignment polytope, where the regular case turns a table of fractional shares into a lottery over whole ones.

What is worth carrying away #

The pattern to take from this is not the marriage metaphor, which is an accident of 1935. It is the form of the statement: this can be done unless there is a reason it cannot, and here is the complete list of reasons.

Most existence theorems are not of that form. They give a sufficient condition, leaving a gap between the cases they settle and the cases that work; a theorem that closes the gap turns a search into a decision, because failing to find the object now proves the obstruction exists, and finding the obstruction proves the object does not. Hall’s theorem is the model of the type, and the fact that so many other results turn out to be it in disguise is the strongest evidence that the form, rather than the marriages, is the content.