# Chapter 58. Hall's Marriage Theorem # Chapter 58. Hall's Marriage Theorem Hall's marriage theorem is one of the central results of combinatorics and graph theory. It gives a complete characterization of when a bipartite graph contains a matching that saturates one side of the graph. The theorem connects local neighborhood structure with global pairing possibilities. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem?utm_source=chatgpt.com)) The theorem is often described through the marriage problem. Suppose a collection of people each has a set of acceptable partners. The question is whether every person can be matched with a distinct acceptable partner. Hall's theorem gives an exact answer. Although the theorem is stated for bipartite graphs, its influence extends into combinatorics, optimization, matrix theory, scheduling, network flows, and design theory. ## 58.1 Bipartite Graphs Let $$ G = (X \cup Y, E) $$ be a bipartite graph. The vertex set is divided into two disjoint parts: $$ X \cap Y = \varnothing, $$ and every edge joins a vertex in \(X\) to a vertex in \(Y\). A matching \(M\) is called an \(X\)-saturating matching if every vertex in \(X\) is matched by \(M\). Thus, $$ \forall x \in X, \quad \exists y \in Y $$ such that $$ xy \in M. $$ Different vertices of \(X\) must be matched to different vertices of \(Y\). The central question is: > When does a bipartite graph contain an \(X\)-saturating matching? Hall's theorem answers this exactly. ## 58.2 Neighborhoods For a vertex $$ x \in X, $$ the neighborhood of \(x\) is the set $$ N(x) = \{y \in Y : xy \in E\}. $$ More generally, for a subset $$ A \subseteq X, $$ the neighborhood of \(A\) is $$ N(A) = \bigcup_{x \in A} N(x). $$ Thus \(N(A)\) contains all vertices in \(Y\) adjacent to at least one vertex in \(A\). For example, suppose $$ A = \{x_1,x_2\}, $$ and $$ N(x_1)=\{y_1,y_2\}, \qquad N(x_2)=\{y_2,y_3\}. $$ Then $$ N(A)=\{y_1,y_2,y_3\}. $$ The neighborhood set measures how many possible partners are available for vertices in \(A\). ## 58.3 Hall's Condition Hall's condition states that for every subset $$ A \subseteq X, $$ the neighborhood satisfies $$ |N(A)| \geq |A|. $$ This condition says that every group of vertices in \(X\) collectively has at least as many available neighbors in \(Y\). |N(A)| \ge |A| The intuition is straightforward. If some subset \(A\) contains more vertices than its neighborhood, then there are not enough distinct vertices in \(Y\) to match all vertices of \(A\). At least two vertices in \(A\) would be forced to share a partner, which is forbidden in a matching. Thus Hall's condition is clearly necessary. The remarkable fact is that it is also sufficient. ## 58.4 Hall's Marriage Theorem **Theorem 58.1. Hall's Marriage Theorem.** Let $$ G = (X \cup Y,E) $$ be a bipartite graph. Then \(G\) contains an \(X\)-saturating matching if and only if for every subset $$ A \subseteq X, $$ $$ |N(A)| \ge |A|. $$ ([en.wikipedia.org](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem?utm_source=chatgpt.com)) This theorem completely solves the bipartite matching problem for one side of the graph. ## 58.5 Necessity of Hall's Condition Suppose \(G\) contains an \(X\)-saturating matching \(M\). Let $$ A \subseteq X. $$ Every vertex in \(A\) is matched to a distinct vertex in \(Y\). Since matching edges are disjoint, distinct vertices in \(A\) must be matched to distinct vertices in \(N(A)\). Therefore, $$ |N(A)| \ge |A|. $$ Thus Hall's condition is necessary. The proof is immediate once the meaning of a matching is understood. ## 58.6 Proof of Sufficiency The converse direction is deeper. We prove Hall's theorem by induction on $$ |X|. $$ Assume Hall's condition holds. ### Case 1 Suppose $$ |N(A)| > |A| $$ for every nonempty proper subset $$ A \subsetneq X. $$ Choose any edge $$ xy \in E. $$ Remove \(x\) and \(y\) from the graph. Let the remaining bipartite graph be $$ G'. $$ We claim Hall's condition still holds in \(G'\). Suppose not. Then some subset $$ A' \subseteq X \setminus \{x\} $$ satisfies $$ |N_{G'}(A')| < |A'|. $$ In the original graph, $$ N_G(A') $$ can differ from $$ N_{G'}(A') $$ by at most the vertex \(y\). Therefore, $$ |N_G(A')| \le |A'|. $$ Since strict inequality is impossible by Hall's condition, we obtain $$ |N_G(A')| = |A'|. $$ But this contradicts the assumption that every proper nonempty subset has strictly larger neighborhood. Thus Hall's condition holds in \(G'\). By induction, \(G'\) has a matching saturating all remaining vertices. Adding the edge \(xy\) gives an \(X\)-saturating matching in \(G\). ### Case 2 Suppose there exists a nonempty proper subset $$ A \subsetneq X $$ such that $$ |N(A)| = |A|. $$ Consider the induced bipartite subgraph on $$ A \cup N(A). $$ Hall's condition holds inside this subgraph, so by induction it contains a matching saturating \(A\). Now remove $$ A \cup N(A) $$ from the graph. Let the remaining graph have parts $$ X' = X \setminus A, \qquad Y' = Y \setminus N(A). $$ We claim Hall's condition holds in the remaining graph. Let $$ B \subseteq X'. $$ Suppose $$ |N_{Y'}(B)| < |B|. $$ Then in the original graph, $$ |N(B \cup A)| < |B| + |A|. $$ But $$ |B \cup A| = |B| + |A|, $$ contradicting Hall's condition. Thus the remaining graph satisfies Hall's condition. By induction it has a matching saturating \(X'\). Combining the two matchings gives a matching saturating all of \(X\). This completes the proof. ## 58.7 Marriage Interpretation Hall's theorem is traditionally described as the marriage problem. Suppose: | Set | Interpretation | |---|---| | \(X\) | Women | | \(Y\) | Men | | Edge \(xy\) | Woman \(x\) is willing to marry man \(y\) | The question asks whether every woman can marry a distinct acceptable man. Hall's condition says: > Every group of women must collectively know at least as many acceptable men as the size of the group. If a set of \(k\) women collectively knows only \(k-1\) men, then distinct marriages are impossible. Hall's theorem states that this obvious obstruction is the only obstruction. Although the terminology is historical, the theorem applies to arbitrary pairing problems. ## 58.8 Perfect Matchings in Bipartite Graphs Suppose $$ |X| = |Y|. $$ Then Hall's theorem implies: A bipartite graph has a perfect matching if and only if Hall's condition holds. Indeed, an \(X\)-saturating matching uses exactly \(|X|\) vertices of \(Y\). Since the two parts have equal size, every vertex in \(Y\) is also matched. Thus the matching is perfect. ## 58.9 Systems of Distinct Representatives Hall's theorem is equivalent to the existence of systems of distinct representatives. Suppose $$ A_1, A_2, \ldots, A_n $$ are finite sets. A system of distinct representatives consists of elements $$ a_i \in A_i $$ such that all chosen elements are distinct. Hall's condition becomes: For every index subset $$ I \subseteq \{1,\ldots,n\}, $$ $$ \left| \bigcup_{i \in I} A_i \right| \ge |I|. $$ Hall's theorem states that this condition is necessary and sufficient for a system of distinct representatives to exist. This formulation is common in combinatorics. ## 58.10 Examples ### Example 1 Let $$ X=\{x_1,x_2,x_3\}, \qquad Y=\{y_1,y_2,y_3\}, $$ with edges $$ x_1y_1, \quad x_1y_2, \quad x_2y_2, \quad x_3y_3. $$ Check Hall's condition. Single vertices have neighborhoods of size at least \(1\). For two-vertex subsets: $$ N(\{x_1,x_2\})=\{y_1,y_2\}, $$ so $$ |N|=2. $$ Similarly, $$ N(\{x_1,x_3\})=\{y_1,y_2,y_3\}, $$ and $$ N(\{x_2,x_3\})=\{y_2,y_3\}. $$ Finally, $$ N(X)=Y. $$ Hall's condition holds, so a perfect matching exists. One example is $$ \{\{x_1,y_1\}, \{x_2,y_2\}, \{x_3,y_3\}\}. $$ ### Example 2 Let $$ X=\{x_1,x_2,x_3\}, \qquad Y=\{y_1,y_2\}, $$ with every edge present. Then $$ N(X)=Y, $$ and $$ |N(X)|=2<3=|X|. $$ Hall's condition fails, so no matching can saturate \(X\). ## 58.11 Regular Bipartite Graphs Hall's theorem immediately implies a major structural result. **Theorem 58.2.** Every \(k\)-regular bipartite graph with \(k \ge 1\) has a perfect matching. ### Proof Let $$ G=(X \cup Y,E) $$ be \(k\)-regular. For any subset $$ A \subseteq X, $$ there are exactly $$ k|A| $$ edges leaving \(A\). All these edges end in \(N(A)\). Since each vertex in \(N(A)\) has degree \(k\), $$ k|A| \le k|N(A)|. $$ Thus, $$ |A| \le |N(A)|. $$ Hall's condition holds. Since regular bipartite graphs satisfy $$ |X|=|Y|, $$ a perfect matching exists. This theorem is fundamental in edge-coloring theory and combinatorial design. ## 58.12 Hall's Theorem and Flows Hall's theorem can be reformulated as a network flow problem. Construct a directed network: | Edge | Capacity | |---|---| | Source to each \(x \in X\) | \(1\) | | Each bipartite edge \(xy\) | \(1\) | | Each \(y \in Y\) to sink | \(1\) | An \(X\)-saturating matching corresponds exactly to a flow of value $$ |X|. $$ Hall's condition becomes equivalent to the max-flow min-cut condition. This interpretation connects matching theory with optimization and algorithm design. ## 58.13 Hall's Theorem and Latin Squares Hall's theorem plays a major role in combinatorial designs. In Latin square completion problems, one often needs to assign symbols to rows or columns without repetition. These assignments become matching problems in bipartite graphs. The theorem also appears in scheduling tournaments, allocating resources, and constructing transversal structures. ## 58.14 Deficiency The deficiency of a bipartite graph measures how far Hall's condition fails. Define $$ \operatorname{def}(G) = \max_{A \subseteq X} (|A|-|N(A)|). $$ Hall's theorem says: $$ \operatorname{def}(G)=0 $$ if and only if an \(X\)-saturating matching exists. Larger deficiencies correspond to larger unavoidable shortages. ## 58.15 Infinite Hall Theorem Hall's theorem extends to infinite bipartite graphs under suitable finiteness assumptions. For countably infinite locally finite bipartite graphs, Hall-type conditions still characterize saturating matchings. These infinite versions require more advanced set-theoretic arguments. ## 58.16 Common Consequences | Statement | Consequence | |---|---| | Hall's condition holds | \(X\)-saturating matching exists | | \(|X|=|Y|\) and Hall holds | Perfect matching exists | | Some subset satisfies \(|N(A)|<|A|\) | Saturating matching impossible | | \(k\)-regular bipartite graph | Perfect matching exists | Hall's theorem converts matching existence into a neighborhood-counting condition. ## 58.17 Historical Notes Hall published the theorem in 1935. It became one of the foundations of modern combinatorics. The theorem later influenced matching algorithms, polyhedral theory, optimization, and network flows. The marriage interpretation made the theorem widely known, but its importance lies in its structural power. It transforms a difficult global existence problem into a family of local counting inequalities. ## 58.18 Exercises 1. Let $$ X=\{x_1,x_2,x_3\}, \qquad Y=\{y_1,y_2,y_3\}, $$ with edges $$ x_1y_1, \quad x_2y_1, \quad x_3y_2. $$ Determine whether Hall's condition holds. 2. Prove that every perfect matching in a bipartite graph satisfies Hall's condition. 3. Show that the complete bipartite graph \(K_{n,n}\) has a perfect matching. 4. Let $$ A_1=\{1,2\}, \quad A_2=\{2,3\}, \quad A_3=\{1,3\}. $$ Find a system of distinct representatives. 5. Give an example of a bipartite graph where Hall's condition fails. 6. Prove that every \(1\)-regular bipartite graph has a perfect matching. 7. Let \(G\) be bipartite. Show that if some subset \(A \subseteq X\) satisfies $$ |N(A)|<|A|, $$ then no matching can saturate \(X\). 8. Prove Hall's theorem for the case \(|X|=2\). 9. Show that every cycle \(C_{2n}\) has a perfect matching by using Hall's theorem. 10. Explain why Hall's theorem implies that every regular bipartite graph has a perfect matching.