In bipartite graph theory and combinatorial optimization, one of the most fundamental questions is: When can every vertex on the left side of a bipartite graph be matched to a distinct vertex on the right side?
While maximum flow and augmenting path algorithms (such as Hopcroft–Karp or Kuhn’s algorithm) allow us to compute a maximum matching for a fixed graph, Hall’s Marriage Theorem (proved by Philip Hall in 1935) gives a clean necessary and sufficient structural condition for a complete matching to exist. In competitive programming, Hall’s theorem often allows us to bypass building an explicit flow network altogether—transforming matching feasibility problems into algebraic inequalities, prefix/interval checks, or Sum Over Subsets Dynamic Programming (SOS DP).
In this post, we will build geometric and combinatorial intuition for Hall’s Marriage Theorem, walk through two classic proofs, explore its most useful generalizations, and solve a classic hard problem: AtCoder ARC106E - Medals.
1. Formal Statement and Intuition
Definitions
Let $G = (L \cup R, E)$ be a bipartite graph with left vertex set $L$, right vertex set $R$, and edges $E \subseteq L \times R$.
- A matching $M \subseteq E$ is a set of edges such that no two edges in $M$ share a common vertex.
- An $L$-saturating matching (or complete matching from $L$ to $R$) is a matching $M$ of size $|M| = |L|$ that covers every vertex in $L$.
- For any subset of left vertices $S \subseteq L$, the neighborhood of $S$, denoted $N_G(S)$ (or simply $N(S)$), is the set of all vertices in $R$ adjacent to at least one vertex in $S$:
Hall’s Marriage Theorem
Theorem (Hall, 1935): A bipartite graph $G = (L \cup R, E)$ has an $L$-saturating matching if and only if for every subset $S \subseteq L$,
\[ |N(S)| \ge |S|. \]This inequality is known as Hall’s Marriage Condition.
Why Local Degree Checks Are Not Enough
A common beginner pitfall is assuming that if $|R| \ge |L|$ and every vertex $u \in L$ has at least one neighbor ($|N(u)| \ge 1$), a complete matching should exist. Consider the two bipartite graphs below:
Figure 1: Left: Hall’s condition holds for every subset $S \subseteq L$, yielding an $L$-saturating matching of size $4$. Right: Every vertex in $L$ has degree $\ge 1$, yet $S = \{u_1, u_2, u_3\}$ only connects to $N(S) = \{v_1, v_2\}$, creating a bottleneck ($|N(S)| = 2 < |S| = 3$).
In the right panel of Figure 1, the three vertices in $S = \{u_1, u_2, u_3\}$ collectively share only two candidate partners $N(S) = \{v_1, v_2\}$. By the Pigeonhole Principle, at most two vertices in $S$ can be matched, no matter how many edges $u_4$ has. Hall’s Marriage Theorem states that the absence of such bottleneck subsets is not just necessary—it is also sufficient to guarantee an $L$-saturating matching.
2. Detailed Proofs of Hall’s Theorem
To establish the theorem completely, we must prove both directions: Necessity ($\implies$) and Sufficiency ($\impliedby$). Below, we present the straightforward necessity proof followed by two distinct proofs of sufficiency:
- Halmos and Vaughan’s Combinatorial Induction (1950) — a purely structural proof using tight/critical subsets.
- Alternating Trees and Augmenting Paths — a constructive, algorithmic proof that directly connects to bipartite matching algorithms.
Direction 1: Necessity ($\implies$)
Suppose $G$ has an $L$-saturating matching $M$. For any vertex $u \in L$, let $M(u) \in R$ denote the unique partner matched to $u$ under $M$.
Take any subset $S \subseteq L$. For each $u \in S$, the edge $(u, M(u))$ belongs to $M \subseteq E$, so $M(u) \in N(S)$. Therefore, the set of matched partners $M(S) = \{M(u) \mid u \in S\}$ is a subset of $N(S)$. Since $M$ is a matching, all vertices in $S$ are matched to distinct vertices in $R$, meaning $|M(S)| = |S|$. Thus:
\[ |N(S)| \ge |M(S)| = |S|. \quad \blacksquare \]Direction 2, Proof 1: Halmos & Vaughan’s Inductive Proof (1950)
We prove sufficiency by strong induction on $|L|$.
Base Case ($|L| = 1$)
If $L = \{u\}$, Hall’s condition for $S = \{u\}$ gives $|N(\{u\})| \ge 1$. Thus $u$ has at least one neighbor $v \in R$, and the single edge $\{(u, v)\}$ forms an $L$-saturating matching.
Inductive Step ($|L| \ge 2$)
Assume Hall’s theorem holds for all bipartite graphs with fewer than $|L|$ left vertices. Given $G = (L \cup R, E)$ satisfying $|N_G(S)| \ge |S|$ for all $S \subseteq L$, we distinguish two cases based on whether any proper non-empty subset of $L$ satisfies Hall’s condition with equality (a tight or critical subset).
Case 1: Every Proper Non-Empty Subset Has Strict Slack
Suppose that for every proper non-empty subset $\emptyset \subsetneq S \subsetneq L$, we have strict inequality:
\[ |N_G(S)| \ge |S| + 1. \]Pick any vertex $u \in L$. Since $|N_G(\{u\})| \ge 1$, we can pick a neighbor $v \in N_G(u)$ and match $u$ with $v$. Now consider the residual graph $G' = G - \{u, v\}$ with left side $L' = L \setminus \{u\}$ and right side $R' = R \setminus \{v\}$.
For any non-empty subset $S \subseteq L'$, $S$ is a proper non-empty subset of $L$. Removing $v$ from $R$ reduces the neighborhood size of $S$ by at most $1$:
\[ |N_{G'}(S)| = |N_G(S) \setminus \{v\}| \ge |N_G(S)| - 1 \ge (|S| + 1) - 1 = |S|. \]Thus, $G'$ satisfies Hall’s condition! By the induction hypothesis, $G'$ has an $L'$-saturating matching $M'$. Adding the edge $(u, v)$ to $M'$ yields an $L$-saturating matching for $G$.
Case 2: There Exists a Tight (Critical) Proper Subset
Suppose there exists some proper non-empty subset $\emptyset \subsetneq S \subsetneq L$ that holds with equality:
\[ |N_G(S)| = |S|. \]We decompose $G$ into two vertex-disjoint subgraphs along $S$ and $N_G(S)$:
- The Critical Subgraph: $G_1 = G[S \cup N_G(S)]$ with left side $S$ and right side $N_G(S)$.
- The Residual Subgraph: $G_2 = G[(L \setminus S) \cup (R \setminus N_G(S))]$ with left side $L \setminus S$ and right side $R \setminus N_G(S)$.
Figure 2: When a proper non-empty subset $S \subsetneq L$ is tight ($|N_G(S)| = |S|$), we match $S$ to $N_G(S)$ in $G_1$ and match $L \setminus S$ to $R \setminus N_G(S)$ in $G_2$.
Let’s verify that both $G_1$ and $G_2$ satisfy Hall’s condition:
- In $G_1$: For any subset $A \subseteq S$, all neighbors of $A$ in $G$ already lie inside $N_G(S)$, so $N_{G_1}(A) = N_G(A)$. Hence $|N_{G_1}(A)| = |N_G(A)| \ge |A|$. Since $|S| < |L|$, the induction hypothesis gives an $S$-saturating matching $M_1$ in $G_1$.
- In $G_2$: Take any subset $T \subseteq L \setminus S$. Consider the union $S \cup T \subseteq L$ in the original graph $G$. Any neighbor of $S \cup T$ in $G$ either belongs to $N_G(S)$ or belongs to $N_G(T) \setminus N_G(S) = N_{G_2}(T)$. Because these two sets are disjoint:
By Hall’s condition on $S \cup T$ in $G$ (and the fact that $S \cap T = \emptyset$), we have:
\[ |N_G(S)| + |N_{G_2}(T)| = |N_G(S \cup T)| \ge |S \cup T| = |S| + |T|. \]Subtracting $|N_G(S)| = |S|$ from both sides yields:
\[ |N_{G_2}(T)| \ge |T|. \]Thus $G_2$ also satisfies Hall’s condition! Since $|L \setminus S| < |L|$, the induction hypothesis gives an $(L \setminus S)$-saturating matching $M_2$ in $G_2$.
Finally, because $G_1$ and $G_2$ are completely vertex-disjoint, $M = M_1 \cup M_2$ is an $L$-saturating matching of $G$. $\blacksquare$
Direction 2, Proof 2: Augmenting Paths and Alternating Trees
We can also prove sufficiency constructively by showing that if a matching $M$ is not $L$-saturating, Hall’s condition forces the existence of an augmenting path.
Let $M$ be a maximum matching in $G$, and suppose for contradiction that $|M| < |L|$. Then there exists at least one unmatched vertex $u_0 \in L$.
Define an alternating path starting at $u_0$ as a simple path whose edges alternate between non-matching edges ($E \setminus M$) and matching edges ($M$):
\[ u_0 \xrightarrow{\notin M} v_1 \xrightarrow{\in M} u_1 \xrightarrow{\notin M} v_2 \xrightarrow{\in M} u_2 \xrightarrow{\notin M} \cdots \]Let $Z$ be the set of all vertices in $G$ reachable from $u_0$ via an alternating path (including $u_0$ itself), and partition $Z$ into its left and right vertices:
\[ Z_L = Z \cap L, \qquad Z_R = Z \cap R. \]We make three key observations about $Z_L$ and $Z_R$:
- Every vertex in $Z_R$ is matched by $M$: If some $v \in Z_R$ were unmatched, the alternating path from $u_0$ to $v$ would start and end at unmatched vertices—which is an augmenting path! Flipping the status of edges along this path (replacing $M$-edges with non-$M$ edges) would create a valid matching of size $|M| + 1$, contradicting the maximality of $M$.
- $|Z_R| = |Z_L| - 1$: Whenever an alternating path reaches $v \in Z_R$ from $Z_L$ via a non-matching edge, we can immediately follow $v$’s unique matching edge $(u', v) \in M$ into $u' \in Z_L \setminus \{u_0\}$. Conversely, every vertex in $Z_L \setminus \{u_0\}$ is entered along its unique matching edge from $Z_R$. Therefore, $M$ induces a one-to-one bijection between $Z_R$ and $Z_L \setminus \{u_0\}$, giving: \[ |Z_R| = |Z_L \setminus \{u_0\}| = |Z_L| - 1. \]
- $N_G(Z_L) = Z_R$: By definition, every $v \in Z_R$ was reached from some vertex in $Z_L$, so $Z_R \subseteq N_G(Z_L)$. Conversely, take any $u \in Z_L$ and any neighbor $v \in N_G(u)$. Since $u$ is reachable from $u_0$ via an alternating path ending with a matching edge (or is $u_0$ itself), taking the edge $(u, v)$ (if not already on the path) shows that $v$ is also reachable via an alternating path, so $v \in Z_R$. Thus $N_G(Z_L) = Z_R$.
Combining Observations 2 and 3 for the subset $S = Z_L \subseteq L$, we obtain:
\[ |N_G(Z_L)| = |Z_R| = |Z_L| - 1 < |Z_L|, \]which directly contradicts Hall’s condition $|N_G(S)| \ge |S|$! Hence no unmatched vertex $u_0 \in L$ can exist, and $|M| = |L|$. $\blacksquare$
Connection to Max-Flow Min-Cut and König’s Theorem: Hall’s Marriage Theorem can also be viewed as a special case of the Max-Flow Min-Cut Theorem (by directing edges from source $s \to L$ with capacity $1$, $L \to R$ with capacity $\infty$, and $R \to t$ with capacity $1$) or König’s Theorem (maximum bipartite matching equals minimum vertex cover).
3. Essential Generalizations for Competitive Programming
In contest problems, Hall’s theorem rarely appears in its bare textbook form. Instead, you will almost always use one of the following three extensions.
1. Hall’s Defect Formula (Maximum Matching Size)
What if Hall’s condition fails for some subsets? Define the deficiency (or defect) of a subset $S \subseteq L$ as $\max(0, |S| - |N(S)|)$. Since at least $|S| - |N(S)|$ vertices in $S$ must remain unmatched, the maximum matching size $\nu(G)$ is bounded by $|L| - (|S| - |N(S)|)$. In fact, equality holds for the worst bottleneck subset:
Theorem (Ore’s / Hall’s Defect Formula): The size of a maximum matching in $G = (L \cup R, E)$ is:
\[ \nu(G) = |L| - \max_{S \subseteq L} \bigl(|S| - |N(S)|\bigr) = \min_{S \subseteq L} \bigl(|L \setminus S| + |N(S)|\bigr). \]
(Note: Setting $S = \emptyset$ gives $|S| - |N(S)| = 0$, so the maximum defect is always $\ge 0$.)
2. Generalized Hall’s Theorem ($K$-Matching / Vertex Capacities)
Suppose each left vertex $u \in L$ needs to be matched to $d(u)$ distinct vertices in $R$ (for example, each employee needs $K$ medals), while each right vertex $v \in R$ can be used at most $1$ time (or more generally, $c(v)$ times).
We can reduce this directly to standard Hall’s theorem by vertex cloning: replace each $u \in L$ with $d(u)$ identical copies $u^{(1)}, u^{(2)}, \dots, u^{(d(u))}$, each connected to the exact same neighborhood $N(u) \subseteq R$.
Observe that for any subset of cloned vertices, if it contains at least one copy of $u$, adding all remaining copies of $u$ increases the subset size without increasing its neighborhood $N(S)$! Thus, the worst-case subsets always include either all $d(u)$ copies of $u$ or none of them:
Theorem (Generalized Hall’s Condition): There exists an assignment where each $u \in L$ receives $d(u)$ matches and each $v \in R$ is used at most $c(v)$ times if and only if for every subset $S \subseteq L$:
\[ \sum_{v \in N(S)} c(v) \ge \sum_{u \in S} d(u). \]In particular, when every $u \in L$ demands $K$ matches and every $v \in R$ has capacity $1$:
\[ |N(S)| \ge K \cdot |S| \quad \forall S \subseteq L. \]
3. The Complement Trick: From Union Size to SOS DP
When $|L| = N \le 20$ and $|R|$ is very large (e.g., $|R| \sim 10^6$), checking $|N(S)| \ge K \cdot |S|$ for all $2^N$ subsets $S \subseteq L$ requires knowing $|N(S)|$ for every subset $S$.
Computing $N(S) = \bigcup_{u \in S} N(u)$ directly is difficult because set union is not additive. However, switching to the complement in $R$ turns the union into a clean subset containment condition!
For each right vertex $v \in R$, let $\text{mask}[v] = N(v) \subseteq L$ be the bitmask of left vertices adjacent to $v$. Then:
- $v \in N(S) \iff \text{mask}[v] \cap S \ne \emptyset$.
- $v \notin N(S) \iff \text{mask}[v] \cap S = \emptyset \iff \text{mask}[v] \subseteq L \setminus S$.
Therefore, if $\text{cnt}[M]$ is the number of right vertices $v \in R$ with $\text{mask}[v] = M$, and we define the Sum Over Subsets (SOS) function:
\[ f(T) = \sum_{T' \subseteq T} \text{cnt}[T'], \]then the number of right vertices not connected to $S$ is simply $f(L \setminus S)$, and the neighborhood size of $S$ is:
\[ |N(S)| = |R| - f(L \setminus S). \]Using SOS DP (Fast Zeta Transform), we can compute $f(T)$ for all $2^N$ masks $T$ in $O(N \cdot 2^N)$ time!
4. Sample Problem: AtCoder ARC106E - Medals
Problem Statement
There are $N$ employees in a company, numbered $1$ to $N$. Employee $i$ follows a strict periodic work schedule determined by an integer $A_i$:
- Come to work for $A_i$ consecutive days ($d = 1, \dots, A_i$),
- Take $A_i$ consecutive days off ($d = A_i + 1, \dots, 2A_i$),
- Come to work for $A_i$ consecutive days ($d = 2A_i + 1, \dots, 3A_i$), and so on.
Each day, the company produces at most one medal and awards it to at most one employee who is present at work on that day.
Find the minimum number of days $D$ needed so that every employee can be awarded at least $K$ medals.
Constraints
- $1 \le N \le 18$
- $1 \le K \le 10^5$
- $1 \le A_i \le 10^5$
Step 1: Monotonicity and a Tight Upper Bound on $D$
First, notice that if $D$ days are sufficient to award $K$ medals to each of the $N$ employees, then $D + 1$ days are also sufficient. This monotonicity means we can binary search for the minimum valid day $D$.
What are the lower and upper bounds for our binary search?
Lower Bound ($L_{\text{bs}} = N K$): Since we need to award $N K$ medals in total and can award at most $1$ medal per day, we need at least $D \ge N K$ days.
Upper Bound ($R_{\text{bs}} = 2 N K$): Why is $D = 2 N K$ always enough, regardless of $A_i$? Let’s analyze how many days employee $i$ works during any prefix of $D$ days. Write $D = q \cdot (2A_i) + r$ with $0 \le r < 2A_i$:
- In the $q$ complete cycles of $2A_i$ days, employee $i$ works $q A_i$ days (exactly half of $2 q A_i$).
- In the remaining $r$ days, because the work phase comes first in each cycle, employee $i$ works $\min(r, A_i)$ days. Since $r < 2A_i$, we always have $\min(r, A_i) \ge \lceil r / 2 \rceil$.
Summing the two parts shows that in the first $D$ days, every employee $i$ is present at work for at least $\lceil D / 2 \rceil$ days!
In particular, when $D = 2 N K$, every single employee is at work for at least $N K$ days. Even if we greedily hand out medals, any subset $S$ of employees has $|N(S)| \ge N K \ge K \cdot |S|$. Thus:
Step 2: Modeling with Generalized Hall’s Theorem
Fix a candidate number of days $D \in [N K, 2 N K]$. Construct a bipartite graph $G = (L \cup R, E)$:
- Left vertices $L = \{0, 1, \dots, N - 1\}$: The $N$ employees. Each employee requires $K$ medals.
- Right vertices $R = \{1, 2, \dots, D\}$: The first $D$ days. Each day can supply at most $1$ medal.
- Edges $E$: There is an edge $(i, d)$ if and only if employee $i$ comes to work on day $d$, which occurs when:
By the Generalized Hall’s Marriage Theorem, $D$ days are sufficient if and only if for every subset of employees $S \subseteq L$:
\[ |N(S)| \ge K \cdot |S|, \]where $N(S) \subseteq \{1, \dots, D\}$ is the set of days on which at least one employee in $S$ is at work.
Step 3: Complement Counting & SOS DP
Since $N \le 18$, there are $2^{18} = 262{,}144$ subsets $S \subseteq L$. Using the Complement Trick from Section 3.3, we represent the set of employees working on day $d$ as an $N$-bit integer $\text{mask}[d] \in [0, 2^N - 1]$:
\[ \text{mask}[d] = \sum_{i \text{ works on day } d} 2^i. \]
Figure 3: For a subset $S \subseteq L$, the days in $R \setminus N(S)$ are precisely the days $d \le D$ where no employee in $S$ works ($\text{mask}[d] \subseteq L \setminus S$). Counting these via SOS DP gives $|N(S)| = D - f(L \setminus S)$.
Let $U = (2^N - 1)$ be the full bitmask of all $N$ employees. For any subset $S \subseteq L$, a day $d \in \{1, \dots, D\}$ does not belong to $N(S)$ if and only if $\text{mask}[d] \cap S = \emptyset$, or equivalently:
\[ \text{mask}[d] \subseteq U \oplus S. \]Thus, to check whether a fixed $D$ is valid:
- Build a frequency array $\text{cnt}[0 \dots 2^N - 1]$ where $\text{cnt}[m]$ counts how many days $d \in \{1, \dots, D\}$ have $\text{mask}[d] = m$.
- Run SOS DP in $O(N 2^N)$ time to compute: \[ f[T] = \sum_{T' \subseteq T} \text{cnt}[T'] \quad \text{for all } T \in [0, 2^N - 1]. \]
- Verify that for every mask $S \in [1, 2^N - 1]$: \[ D - f[U \oplus S] \ge K \cdot \operatorname{popcount}(S). \]
Performance Optimization: Instead of recomputing employee attendance from scratch inside each binary search iteration, we can precompute the array
mask[1 .. 2NK]once before the binary search in $O(N \cdot NK) = O(N^2 K)$ time! Insidecheck(D), buildingcntis then just a fast $O(D)$ loop.
Step 4: Walkthrough on Sample 1
Consider Sample 1: $N = 3$, $K = 3$, and $A = [1, 2, 3]$. Here $N K = 9$ and $2 N K = 18$. Let’s inspect the daily attendance bitmasks for the first $D = 10$ days:
| Day $d$ | Emp 0 ($A_0=1$) | Emp 1 ($A_1=2$) | Emp 2 ($A_2=3$) | $\text{mask}[d]$ (binary) |
|---|---|---|---|---|
| $1$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | 111 ($7$) |
| $2$ | $\cdot$ | $\checkmark$ | $\checkmark$ | 110 ($6$) |
| $3$ | $\checkmark$ | $\cdot$ | $\checkmark$ | 101 ($5$) |
| $4$ | $\cdot$ | $\cdot$ | $\cdot$ | 000 ($0$) |
| $5$ | $\checkmark$ | $\checkmark$ | $\cdot$ | 011 ($3$) |
| $6$ | $\cdot$ | $\checkmark$ | $\cdot$ | 010 ($2$) |
| $7$ | $\checkmark$ | $\cdot$ | $\checkmark$ | 101 ($5$) |
| $8$ | $\cdot$ | $\cdot$ | $\checkmark$ | 100 ($4$) |
| $9$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | 111 ($7$) |
| $10$ | $\cdot$ | $\checkmark$ | $\cdot$ | 010 ($2$) |
- Why $D = 9$ fails: Look at Day $4$, where $\text{mask}[4] = \texttt{000}_2$ (nobody comes to work). For the full set $S = \{0, 1, 2\}$ ($|S| = 3$), its complement is $U \oplus S = \texttt{000}_2$, and $f[\texttt{000}_2] = \text{cnt}[\texttt{000}_2] = 1$ (Day $4$). Thus at $D = 9$: \[ |N(\{0, 1, 2\})| = 9 - f[\texttt{000}_2] = 9 - 1 = 8 < K \cdot |S| = 9. \]
- Why $D = 10$ succeeds: At $D = 10$, $|N(\{0, 1, 2\})| = 10 - 1 = 9 \ge 9$, and every single-employee and two-employee subset also satisfies $10 - f[U \oplus S] \ge 3|S|$. Thus the minimum number of days is $10$.
Complexity Analysis
- Time Complexity:
- Precomputation: Marking work intervals for each of the $N$ employees up to $2NK$ takes $O(N \cdot 2NK) = O(N^2 K)$ operations ($\approx 6.4 \times 10^7$ simple bitwise ORs).
- Binary Search: The search range $[NK, 2NK]$ has length $NK \le 1.8 \times 10^6$, requiring $\lceil \log_2(NK) \rceil \le 21$ iterations. Each call to
check(D)takes $O(D)$ to populatefand $O(N 2^N)$ for the SOS DP. - Total Time: \[ O\bigl(N^2 K + (N K + N 2^N) \log(N K)\bigr). \] For $N = 18$ and $K = 10^5$, $N 2^N \approx 4.7 \times 10^6$, which runs in $\sim 0.25$ seconds in C++.
- Space Complexity: $O(N K + 2^N)$ to store
day_mask(size $3.6 \times 10^6$) and the SOS DP arrayf(size $2^{18} = 262{,}144$), using less than $18\text{ MB}$ of memory.
5. Summary Cheat Sheet
| Variant / Technique | Mathematical Formulation | Typical Use Case |
|---|---|---|
| Standard Hall’s Theorem | $\forall S \subseteq L,\; \lvert N(S)\rvert \ge \lvert S\rvert$ | Proving existence of an $L$-saturating matching |
| Hall’s Defect Formula | $\nu(G) = \lvert L\rvert - \max_{S \subseteq L} (\lvert S\rvert - \lvert N(S)\rvert)$ | Finding maximum matching size when bottlenecks exist |
| Generalized $K$-Matching | $\forall S \subseteq L,\; \lvert N(S)\rvert \ge K \cdot \lvert S\rvert$ | Assigning $K$ distinct resources to each left vertex |
| Complement + SOS DP | $\lvert N(S)\rvert = \lvert R\rvert - \sum_{T \subseteq L \setminus S} \text{cnt}[T]$ | Fast $O(N 2^N)$ verification when $\lvert L\rvert \le 20$ and $\lvert R\rvert$ is large |