Lemma › Guides › Hall's marriage theorem: statement, proof and uses
Guide

Hall's marriage theorem: statement, proof and uses

Hall's marriage theorem says when every boy can be given a different girl he knows: if and only if every group of boys knows at least as many girls as it has boys. It is the tool you take out when a problem says "assign each of these a different one of those", and it turns an existence question into a condition you can check by looking at groups.

The statement

You have a set of boys and a set of girls. Each boy knows some of the girls. A matching that covers all the boys pairs each boy with a girl he knows, with no girl used twice. Hall's theorem says it exists if and only if

∣N(S)∣≥∣S∣for every group S of boys,|N(S)| \ge |S| \quad \text{for every group } S \text{ of boys,}

where N(S)N(S) is the set of girls known by at least one boy in SS. In words: every group of boys, taken together, knows at least as many girls as there are boys in the group.

The same statement appears in other clothes. A family of sets A1,…,AmA_1, \dots, A_m has a system of distinct representatives, one element xi∈Aix_i \in A_i with all xix_i different, if and only if any kk of the sets together contain at least kk elements.

The easy half

If a matching exists, the condition holds. Take any group of kk boys. They are matched to kk different girls, and all of those girls are among the girls they know. So they know at least kk girls.

The hard half is the other direction. If no group is crowded, a matching exists. The proof is by induction on the number of boys.

The proof

For one boy it is clear: he knows at least one girl. Suppose the statement is true for fewer than mm boys and take mm boys satisfying the condition.

Case 1. Every group of kk boys, with 1≤k<m1 \le k < m, knows at least k+1k + 1 girls. Pair any boy with any girl he knows. Remove both. Every remaining group of kk boys has lost at most one girl, so it still knows at least kk. The condition holds for the rest, and induction finishes it.

Case 2. Some group SS of kk boys, 1≤k<m1 \le k < m, knows exactly kk girls. That group, by itself, satisfies the condition, so by induction it can be matched into its kk girls. Now look at the remaining boys against the remaining girls. Take a group TT of the remaining boys. Together S∪TS \cup T knows at least ∣S∣+∣T∣|S| + |T| girls, and SS accounts for only kk of them. So TT knows at least ∣T∣|T| girls outside N(S)N(S), and the condition holds for the rest. The induction hypothesis applies to these remaining boys and the girls outside N(S)N(S), because there are fewer than mm of them, and it gives them a matching that cannot clash with the one for SS.

Both cases end with a full matching. The idea to remember is the split: either there is slack everywhere, or there is a group with no slack that you can match on its own first.

An example with the condition checked

A deck has 1313 ranks and 44 suits, so 5252 cards. Deal it into 1313 piles of 44 cards, any way at all. Can you always take one card from each pile so that the 1313 cards you take have different ranks?

Yes. Treat the piles as the sets. Take any kk piles. They hold 4k4k cards in total, and each rank has only 44 cards, so those cards cover at least kk ranks. That is the condition for kk piles to have distinct representatives. Hall's theorem finishes it.

A small version you can check by hand: 99 cards in 33 ranks with 33 cards each, dealt into 33 piles of 33. Treating cards of one rank as identical, there are 16801680 ways to deal them, and every one admits three cards of three different ranks, one from each pile.

The shape of a failure

Hall's condition fails when some group is crowded. Take the sets {1,2}\{1,2\}, {1,2}\{1,2\} and {1,2}\{1,2\}. Three sets, but together they contain only 22 elements. No choice of distinct representatives exists, and this is a certificate that you can write down in one line.

That is the second use of the theorem. When you cannot find a matching, a group that violates the condition is exactly what proves there is none. There is also a quantitative version. The largest matching has size m−dm - d, where dd is the biggest value of ∣S∣−∣N(S)∣|S| - |N(S)| over all groups SS, including the empty one. For the three sets above, d=1d = 1 and the best you can do is 22 pairs.

Regular graphs: the most common use

Suppose every boy knows exactly dd girls and every girl is known by exactly dd boys, for some d≥1d \ge 1. Then a perfect matching exists. Take a group of kk boys. They have dkdk acquaintances in total, counting repeats. Each girl accounts for at most dd of those, so the group knows at least kk girls.

This works for a table of 00s and 11s with the same number dd of ones in each row and each column: you can always pick nn of the ones that lie in different rows and different columns. Among the 4×44 \times 4 tables with exactly two ones in each row and column there are 9090, and each one contains such a selection.

When to reach for it

Traps

Check the condition for every group, not for single boys. A pair can fail when each member is fine alone, as in {1},{1}\{1\}, \{1\}.

The condition is one-sided. It guarantees that the boys are all matched, and says nothing about the girls. If there are more girls than boys, some girls stay single, and that is fine.

Finally, the theorem tells you a matching exists. To find one, run an augmenting path search or build it by hand along the proof.

This lives in the family of extremal graph arguments: you show that any obstruction would be a crowded group and then rule that out, so you never build the object. For practice, find three problems that start "assign" and write the condition in the form "any kk of the items have at least kk options" before you do anything else. The problem archive is where to look.

Related guides

Techniques in this guide

Competitions this guide helps with

Train it on Lemma

Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.

Find your level