11.5. Bipartite Graphs & Matchings 309
ChuckTomMichaelJohnAliceMarthaSaraJaneMergatroidFigure 11.10 One possible matching for the men is shown with bold edges. For
example, John is matched with Mergatroid.
at least one of those men. For example, the set of women liked by Tom and John in
Figure 11.9 consists of Martha, Sarah, and Mergatroid. For us to have any chance
at all of matching up the men, the followingmatching conditionmust hold:
The Matching Condition: every subset of men likes at least as large a set of women.
For example, we can not find a matching if some set of 4 men like only 3 women.
Hall’s Theorem says that this necessary condition is actually sufficient; if the match-
ing condition holds, then a matching exists.
Theorem 11.5.2.A matching for a setMof men with a setW of women can be
found if and only if the matching condition holds.
Proof. First, let’s suppose that a matching exists and show that the matching condi-
tion holds. For any subset of men, each man likes at least the woman he is matched
with and a woman is matched with at most one man. Therefore, every subset of
men likes at least as large a set of women. Thus, the matching condition holds.
Next, let’s suppose that the matching condition holds and show that a matching
exists. We use strong induction onjMj, the number of men, on the predicate:
P.m/WWDif the matching condition holds for a set,M,
ofmmen, then there is a matching forM.Base case(jMj D 1 ): IfjMj D 1 , then the matching condition implies that the
lone man likes at least one woman, and so a matching exists.