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 Cancel reply