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
where is the set of girls known by at least one boy in . 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 has a system of distinct representatives, one element with all different, if and only if any of the sets together contain at least elements.
The easy half
If a matching exists, the condition holds. Take any group of boys. They are matched to different girls, and all of those girls are among the girls they know. So they know at least 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 boys and take boys satisfying the condition.
Case 1. Every group of boys, with , knows at least girls. Pair any boy with any girl he knows. Remove both. Every remaining group of boys has lost at most one girl, so it still knows at least . The condition holds for the rest, and induction finishes it.
Case 2. Some group of boys, , knows exactly girls. That group, by itself, satisfies the condition, so by induction it can be matched into its girls. Now look at the remaining boys against the remaining girls. Take a group of the remaining boys. Together knows at least girls, and accounts for only of them. So knows at least girls outside , and the condition holds for the rest. The induction hypothesis applies to these remaining boys and the girls outside , because there are fewer than of them, and it gives them a matching that cannot clash with the one for .
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 ranks and suits, so cards. Deal it into piles of cards, any way at all. Can you always take one card from each pile so that the cards you take have different ranks?
Yes. Treat the piles as the sets. Take any piles. They hold cards in total, and each rank has only cards, so those cards cover at least ranks. That is the condition for piles to have distinct representatives. Hall's theorem finishes it.
A small version you can check by hand: cards in ranks with cards each, dealt into piles of . Treating cards of one rank as identical, there are 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 , and . Three sets, but together they contain only 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 , where is the biggest value of over all groups , including the empty one. For the three sets above, and the best you can do is pairs.
Regular graphs: the most common use
Suppose every boy knows exactly girls and every girl is known by exactly boys, for some . Then a perfect matching exists. Take a group of boys. They have acquaintances in total, counting repeats. Each girl accounts for at most of those, so the group knows at least girls.
This works for a table of s and s with the same number of ones in each row and each column: you can always pick of the ones that lie in different rows and different columns. Among the tables with exactly two ones in each row and column there are , and each one contains such a selection.
When to reach for it
- "Assign to each a different ..." with options listed per item. Rooms to guests, or jobs to workers.
- A regular structure. Every row, column, pile or vertex has the same degree.
- Proving a rectangle can be completed. The standard argument that a Latin rectangle with fewer rows than columns can be extended by one more row is Hall's theorem applied to the unused symbols in each column.
- A claim that is believable, where building the assignment by hand is messy. State the condition for every group and skip the construction.
Traps
Check the condition for every group, not for single boys. A pair can fail when each member is fine alone, as in .
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 of the items have at least options" before you do anything else. The problem archive is where to look.
Related guides
- Ramsey problems for beginners: one move, four levelsRamsey olympiad problems in order of difficulty, from six people to three colours and number puzzles. One vertex, pigeonhole its edges, then look inside.
- Extremal graph problems for beginners: the bound and the exampleAn extremal graph problem is two problems: a bound nobody can beat and an example that reaches it. How to spot one, and which vertex to pick first.
- The extremal principle: how to choose which extreme to takeTaking the largest or the smallest is the easy half. The three signals that call for an extreme, and the one question that tells you if you picked the right one.
- Catalan numbers in competition math: what they countCatalan numbers count balanced brackets, paths under a diagonal, triangulations and non-crossing pairings. The formula, a proof, and how to spot them.
- Chicken McNugget theorem: the proof and the formulaFor coprime a and b the largest total you cannot make is ab - a - b. The proof, the count of unmakeable totals, and what breaks with three sizes.
Techniques in this guide
- The Extremal Principle in GraphsTake the longest path, the vertex of largest degree.
Competitions this guide helps with
- AMC 1225 multiple-choice questions · 75 minutes
- Euclid10 questions, a mix of answer-only and full-solution parts · 2.5 hours
- COMC12 questions in three parts: four short answers, four longer answers and four full solutions · 2.5 hours
- UKMT Senior Challenge25 questions: 22 multiple choice and, as a trial from 2026, three with a three-digit answer from 000 to 999 · 90 minutes
- BMO Round 1six problems needing full written solutions, the first intended to be more accessible than the rest · 3.5 hours
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