Matchings and minimum degree

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.

Leave a Reply

Your email address will not be published.