Matchings and minimum degree

A Tale of Two Halls

(Philip) Hall’s theorem.  Let G be a bipartite graph on vertex classes X, Y.  Suppose that,  for every S \subseteq X, |N(S)| \geq |S|.  Then there is a matching from X to Y.

This is traditionally called Hall’s marriage theorem.  The picture is that the people in X are all prepared to marry some subset of the people in Y.  If some k people in X are only prepared to marry into some set of k-1 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 Y.

Proof. Suppose first that |N(S)| > |S| for all S \subset X.  Then we can match any element of X arbitrarily to a neighbour in Y and obtain a smaller graph on which Hall’s condition holds, so are done by induction.

Otherwise |N(S)| = |S| for some S \subset X.  By induction there is a matching from S to N(S).  Let T = X \setminus S.  Then for any U \subseteq T we have

    \[|N(U) \setminus N(S)| + |N(S)| = |N(U \cup S)| \geq |U \cup S| = |U| + |S|\]

hence |N(U) \setminus N(S)| \geq |U| and Hall’s condition holds on (T, Y \setminus N(S)).  So by induction there is a matching from T to Y \setminus N(S), which together with the matching from S to N(S) is a matching from X to Y. \square

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

Proof. Counted with multiplicity, |N(S)| = k|S|.  But each element of Y is hit at most k times, so |N(S)| \geq k|S| / k = |S| in the conventional sense. \square

Corollary 2. Let G be a spanning subgraph of K_{n,n} with minimum degree at least n/2.  Then G has a perfect matching.

This is very slightly more subtle.

Proof. If |N(S)| = n there is nothing to check.  Otherwise there is a y \in Y \setminus N(S).  Then N(y) \subseteq X \setminus S and |N(y)| \geq n/2, so |S| \leq n/2.  But |N(S)| \geq n/2 for every S. \square

Schrijver proved that a k-regular bipartite graph with n vertices in each class in fact has at least \left(\frac {(k-1)^{k-1}} {k^{k-2}}\right)^n perfect matchings.  For minimum degree k we have the following.

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

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 S on which it is tight.  Fix x \in S and match it arbitrarily to a neighbour y \in Y.  (Philip) Hall’s condition still holds on (S - x, Y-y) and the minimum degree on this subgraph is at least k-1, so by induction we can find at least (k-1)! perfect matchings.  Since there were at least k choices for y we have at least k! perfect matchings from S to N(S).  These extend to perfect matchings from X to Y as in the proof of (Philip) Hall’s theorem. \square

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

Leave a Reply

Your e-mail address will not be published.