Lesson 2

Theorem (Hall's Marriage Theorem, 1935). Consider a bipartite graph \(G = (U \sqcup V, E)\). There exists a matching that covers every vertex in \(U\) if and only if for every subset \(S \subseteq U\), the size of its neighborhood satisfies \(|N(S)| \ge |S|\).

Proof. The “only if” direction is still straightforward. If we have a matching that covers \(U\), then for any subset \(S \subseteq U\), each vertex in \(S\) is matched to a unique vertex in \(N(S)\). Thus, \(|N(S)|\) must be at least \(|S|\).

For the “if” direction, assume the condition holds. We construct a poset \(P\) on the set of vertices \(U \sqcup V\). We define the relation \(x \prec y\) if and only if \(x \in U\), \(y \in V\), and there is an edge \((x,y) \in E\).

Let \(w\) be the size of a maximum antichain. By Dilworth's theorem, \(P\) can be partitioned into \(w\) chains. Let the partition consist of \(k_{1}\) chains of size 1 (single vertices) and \(k_{2}\) chains of size 2 (edges). The total number of vertices is \(|U| + |V| = k_{1} + 2k_{2} = w + k_{2}\). Hence, we get \(k_{2} = |U| + |V| - w\). The \(k_{2}\) chains of size 2 form a matching of size \(k_{2}\). We want to show this matching covers \(U\), which means its size must be \(|U|\).

Let's find an upper bound on \(w\). Let \(A\) be a maximum antichain in \(P\). Let \(A_{U} = A \cap U\) and \(A_{V} = A \cap V\). By the definition of an antichain in our poset, there are no edges between any vertex in \(A_{U}\) and any vertex in \(A_{V}\). This means that the neighborhood of \(A_{U}\) is completely contained in the complement of \(A_{V}\): \(N(A_{U}) \subseteq V \setminus A_{V}\). Using the marriage condition for the set \(A_{U}\), we have \(|A_{U}| \le |N(A_{U})|\). Combining these facts, we get \(|A_{U}| \le |N(A_{U})| \le |V \setminus A_{V}| = |V| - |A_{V}|\). Rearranging gives \(|A_{U}| + |A_{V}| \le |V|\). Since \(w = |A| = |A_{U}| + |A_{V}|\), we have \(w \le |V|\).

Now we can plug this back into our expression for the matching size: \[k_{2} = |U| + |V| - w \ge |U|.\] Thus, we have found a matching of size at least \(|U|\).◼