*A Tale of Two Halls*

**(Philip) Hall’s theorem.** *Let be a bipartite graph on vertex classes , . Suppose that, for every , . Then there is a matching from to .*

This is traditionally called Hall’s marriage theorem. The picture is that the people in are all prepared to marry some subset of the people in . If some people in are only prepared to marry into some set of people, then we have a problem; but this is the only problem we might have. There is no room in this picture for the preferences of people in .

*Proof.* Suppose first that for all . Then we can match any element of arbitrarily to a neighbour in and obtain a smaller graph on which Hall’s condition holds, so are done by induction.

Otherwise for some . By induction there is a matching from to . Let . Then for any we have

hence and Hall’s condition holds on . So by induction there is a matching from to , which together with the matching from to is a matching from to .

**Corollary 1.** * Every -regular bipartite graph has a perfect matching.*

*Proof.* Counted with multiplicity, . But each element of is hit at most times, so in the conventional sense.

**Corollary 2.** *Let be a spanning subgraph of with minimum degree at least . Then has a perfect matching.*

This is very slightly more subtle.

*Proof.* If there is nothing to check. Otherwise there is a . Then and , so . But for every .

Schrijver proved that a -regular bipartite graph with vertices in each class in fact has at least perfect matchings. For minimum degree we have the following.

**(Marshall) Hall’s theorem.** *If each vertex of has degree at least and there is at least one perfect matching then there are at least .*

This turns out to be easy if we were paying attention during the proof of (Philip) Hall’s theorem.

*Proof.* By (Philip) Hall’s theorem the existence of a perfect matching means that (Philip) Hall’s condition holds. Choose a minimal on which it is tight. Fix and match it arbitrarily to a neighbour . (Philip) Hall’s condition still holds on and the minimum degree on this subgraph is at least , so by induction we can find at least perfect matchings. Since there were at least choices for we have at least perfect matchings from to . These extend to perfect matchings from to as in the proof of (Philip) Hall’s theorem.

Thanks to Gjergji Zaimi for pointing me to (Marshall) Hall’s paper via MathOverflow.