Halls marriage theorem
Halls marriage theorem, from graph theory, is an excellent example of induction. It is called the marriage
theorem because traditionally it is stated in terms of men and women, but well instead use robots and batteries.
Say we have a set R of n robots and a set B of n batteries. Each robot submits a list of batteries it likes. The
question were trying to answer is when we can pair off robots and batteries so that each robot gets assigned a
battery it likes. Lets think about some examples.
Example 1. Say we have robots r1 , r2 and r3 , and batteries b1 , b2 and b3 . Robot r1 likes batteries b1 and b2 , robot
r2 likes battery r2 and robot r3 likes batteries r1 and r3 . Lets depict this as follows.
r1 b1
r2 b2
r3 b3
Here, we can find a matching. We have to give battery r2 to b2 , then we have to give battery b1 to r1 , since b2 has
already been taken, which means we have to give battery b3 to r3 .
Example 2. Say we have the following situation.
r1 b1
r2 b2
r3 b3
Here, we cant have a matching: there are 3 robots, but they collectively like only 2 batteries, so theres no way
there can be a matching.
Example 3. Heres a slightly less transparent situation where a matching doesnt exist.
r1 b1
r2 b2
r3 b3
r4 b4
Here, every battery is liked by some robot. But if we look at the set of batteries liked by robots r1 , r2 and r3 , it
consists of only b1 and b2 , so theres no way we can assign to each robot a battery that it likes because theres no
way to share 2 batteries amongst 3 robots.
It turns out that the problem described in examples 2 and 3 is the only thing that can go wrong. More precisely,
Theorem 4 (Halls marriage theorem). A matching between robots and batteries exists if and only if, for every
subset X B of robots, the set of batteries Y B liked by robots in X is at least as big as X.
1
The condition of the theorem is often called the matching condition. Well abbreviate it to MC.
Proof. We induct on the number n of robots and batteries. More precisely, let P (n) be the statement that if we
have n robots and n batteries and MC is satisfied, then a matching exists.
The base case, P (1), is easy. If we have only one robot, then MC says that that robot must like at least one
battery, so we match up our lone robot with our lone battery and were done.
We now proceed by strong induction. Were assuming P (1), . . . , P (k) and trying to prove P (k + 1), so suppose
we have k + 1 robots and k + 1 batteries and that MC is satisfied. Lets split up into two cases.
Case 1 is when every proper subset of robots like a strictly larger number of batteries. See example 5 below for
an example of this situation. Pick any robot r and pick a battery b that r likes. Pair them off. Now we want to
show that R {r} and B {b} also satisfy MC, and then we can apply P (k) to conclude that there is a matching
between these two sets too. To see that these satisfy MC, let X R {r} and let Y be the set of batteries liked
by some robot in X. Our assumption in this case is that |X| < |Y |. Notice that |Y {b}| is either equal to |Y | 1
or equal to |Y |, depending on whether or not b Y . In any case, this means that |X| |Y {b}|. This means
that MC is satisfied for R {r} and B {b}, so we can find a matching between these robots and batteries using
P (k 1). Weve already paired off r and b, so weve constructed a matching between R and B.
Case 2, then, is when there is a proper subset S of robots that likes exactly as many batteries (we know that
MC is satisfied, so every subset likes at least as many batteries, and if its not strictly greater, then it has to be
equal). (Example 1 is of this form, since the set of robots {r2 } has only one element, and likes only one battery.)
Let |S| = m and let T be the set of m batteries liked by robots in S. Clearly MC is satisfied for S and T , so by
P (m) we know that there is a matching between these two sets.
So now we need to find a matching between R S and B T . Both of these sets have (k + 1) m elements, so
we want to use P (k + 1 m), but to do that we need to check that MC is also satisfied by these two sets. So let
X R S be a set of robots in R S. Let Y be the set of robots liked by X excluding those that are in T . Now
notice that Y T is precisely the set of batteries liked by robots in X S. Indeed, every battery in Y is liked by
some robot in X, and every battery in T is liked by some robot in S, and conversely, all robots in X like batteries
that are either in Y or in T , and all robots in S like batteries in S. So the MC tells us that
|X S| |Y T |.
But notice that X and S are disjoint sets, so |X S| = |X| + |S|, and similarly Y and T are disjoint too so
|Y T | = |Y | + |T |. Since |S| = |T | = m, we can subtract m from both sides of our equation and get that
|X| |Y |.
This shows that MC is satisfied for R S and B T . So by P (k + 1 m), a matching exists between these two
sets also. We now put together the matching of S and T with the matching of R S and B T to get a matching
of all of R with all of B.
Example 5. Consider the following situation.
r1 b1
r2 b2
r3 b3
This is an example of case 1. Each single robot likes 2 batteries, and each pair of robots like 3 batteries, which
means that all proper subset of robots like a strictly larger number of batteries.