Matchings and Hall's Theorem

Suppose a company has several job openings and a pool of applicants. Each applicant is qualified for only some of the jobs. Can every job be filled by a distinct qualified applicant? This is the marriage problem in disguise. It is the central question this article answers completely. The tool for answering it is Hall's Marriage Theorem. It gives an exact combinatorial test for when such a perfect assignment exists. This test is checkable in principle by inspecting subsets of applicants. Matchings sit at the intersection of pure structural graph theory and algorithmic combinatorics. They model assignment problems: workers to jobs, students to schools, organs to patients, kidneys to donors in exchange programs. The mathematical question "does a matching saturating one side exist" turns out to be equivalent to a purely set-theoretic condition. That condition concerns neighborhoods of subsets. The equivalence follows from a short and beautiful argument. This equivalence is one of the earliest and cleanest examples of what is now called a min-max theorem. It is an existence statement paired with an easily verifiable certificate of non-existence. The big picture is that Hall's condition is not just a theoretical curiosity. It is constructive. The proof we present builds matchings directly using augmenting paths. This is an algorithmic idea that generalizes far beyond bipartite graphs. It becomes the engine behind network flow algorithms. Understanding augmenting paths here is the correct on-ramp to the max-flow/min-cut circle of ideas. It also leads to König's theorem, which reinterprets the same structure in terms of vertex covers. This article gives the formal definitions of matchings and augmenting paths. It states and completely proves Hall's theorem via the augmenting path method. It derives the deficiency version and the corollary for regular bipartite graphs. It works through two nontrivial numerical examples. Finally, it shows exactly which hypothesis is essential. It does so by exhibiting a graph where dropping it breaks the theorem.

Key takeaways
  • A matching is a set of edges no two of which share an endpoint; we ask when a matching can saturate every vertex on one side of a bipartite graph.
  • Hall's condition: every subset SS of one side has ∣N(S)∣≥∣S∣|N(S)| \geq |S|, where N(S)N(S) is the set of neighbors of SS.
  • Hall's Marriage Theorem: a bipartite graph has a matching saturating side XX if and only if Hall's condition holds for every S⊆XS \subseteq X.
  • The proof works via augmenting paths: an unmatched vertex reachable by an alternating path to another unmatched vertex lets us flip the matching to grow it by one edge.
  • The deficiency version quantifies partial failure: the maximum matching size equals ∣X∣−max⁡S⊆X(∣S∣−∣N(S)∣)|X| - \max_{S \subseteq X}(|S| - |N(S)|).
  • Key idea: local neighborhood-counting is exactly as powerful as global matching existence — checking finitely many subset inequalities decides the entire assignment problem.

Where this lives today

Hall's theorem and the augmenting path method underlie modern algorithms for bipartite matching used in assignment problems: matching residents to hospitals (the stable marriage variant builds directly on this machinery), matching students to schools in centralized admissions systems, and assigning tasks to processors in scheduling. In combinatorial optimization, Hall's theorem is the bipartite special case of the max-flow min-cut theorem, viewing the bipartite graph as a flow network with unit capacities; this is the natural bridge to Network Flows and Max-Flow Min-Cut. The deficiency version generalizes to weighted and capacitated settings used in transportation and logistics planning. In algebra and combinatorics, systems of distinct representatives arising from Hall's theorem appear in the theory of transversal matroids and in proving the existence of Latin squares and Latin rectangle completions — a Latin rectangle can always be extended to a Latin square precisely because the relevant bipartite graph of "available symbols per row" satisfies Hall's condition. In coding theory and cryptography, perfect matchings in regular bipartite graphs (guaranteed by the regular-graph corollary above) underlie constructions of expander-based codes and certain key-exchange protocols using bipartite graph structures. The dual viewpoint — minimum vertex covers rather than maximum matchings — is the subject of König's Theorem and Vertex Covers, which shows the same augmenting-path obstruction set constructed in the proof above is literally a minimum vertex cover in disguise. Understanding Bipartite Graphs and Characterization is what makes all of this meaningful in the first place, since Hall's condition is stated purely in terms of the two-sided structure that characterization result identifies.

Ask the tutor: Can you show me step by step how the augmenting-path algorithm finds a maximum matching in a specific 6-vertex bipartite graph I give you?

DefinitionMatchings, saturation, and Hall's condition

Let G=(X∪Y,E)G = (X \cup Y, E) be a bipartite graph with parts XX and YY, and no other assumptions on the sizes of X,YX, Y or the edge set. A matching M⊆EM \subseteq E is a set of edges such that no two edges of MM share an endpoint. Equivalently, every vertex of GG is incident to at most one edge of MM. A vertex vv is saturated by MM (or MM-saturated) if some edge of MM is incident to vv; otherwise vv is MM-exposed. A matching MM saturates a set SS if every vertex of SS is MM-saturated. A matching is perfect if it saturates X∪YX \cup Y (so in particular ∣X∣=∣Y∣|X| = |Y|). For a set S⊆XS \subseteq X, the neighborhood N(S)⊆YN(S) \subseteq Y is

N(S)={y∈Y:∃x∈S, xy∈E}.N(S) = \{ y \in Y : \exists x \in S,\ xy \in E \}.

GG satisfies Hall's condition (relative to XX) if

∣N(S)∣≥∣S∣for every S⊆X.|N(S)| \geq |S| \quad \text{for every } S \subseteq X.

An MM-alternating path is a path whose edges alternate between E∖ME \setminus M and MM. An MM-augmenting path is an MM-alternating path whose two endpoints are both MM-exposed (in particular it has odd length, starting and ending with an edge not in MM).

Intuition

Picture XX as a set of job seekers and YY as a set of jobs, with an edge whenever a seeker is qualified for a job. A matching pairs seekers with jobs they are qualified for, one-to-one. We want to know: can every seeker be placed? The naive local obstruction is obvious — if three seekers are collectively qualified for only two jobs, no matter how cleverly you assign, at least one of the three goes unplaced, since two jobs cannot absorb three distinct people. Hall's theorem is the surprising converse: if no such local obstruction exists anywhere among any subset of seekers, then a full placement is always possible. There is no hidden global obstruction lurking beyond the subset-counting ones. The engine that proves this is the augmenting path. Start with any matching, possibly nothing at all. If some vertex x0∈Xx_0 \in X is unmatched, look for an alternating path from x0x_0 that ends at an unmatched vertex yk∈Yy_k \in Y, alternating "non-matching edge, matching edge, non-matching edge, ...". Flipping the roles of matched and unmatched edges along this path — matching edges become non-matching and vice versa — produces a new matching with exactly one more edge, and x0x_0 is now matched. Repeating this process, one exposed vertex at a time, either eventually saturates all of XX, or gets stuck: no augmenting path exists from some exposed x0x_0. It is precisely at this stuck point that we can extract a Hall-violating set, turning the algorithmic failure into a certificate.

Figure
A bipartite graph with X = {x1,x2,x3,x4} and Y = {y1,y2,y3,y4}; matching edges are bold, an augmenting path is highlighted
x₁ x₂ x₃ x₄ y₁ y₂ y₃ y₄ augmenting path: x₄ → y₄ (both exposed)

Central theorem

TheoremHall's Marriage Theorem

Let G=(X∪Y,E)G = (X \cup Y, E) be a bipartite graph in which XX and YY are finite vertex sets (possibly of different sizes) and every edge joins a vertex of XX to a vertex of YY. Then GG has a matching that saturates XX if and only if

∣N(S)∣≥∣S∣for every subset S⊆X.|N(S)| \geq |S| \qquad \text{for every subset } S \subseteq X.
LemmaAugmenting path lemma

Let MM be a matching in a bipartite graph G=(X∪Y,E)G = (X \cup Y, E) and let M′M' be a matching with ∣M′∣>∣M∣|M'| > |M|. Then the symmetric difference M△M′=(M∖M′)∪(M′∖M)M \triangle M' = (M \setminus M') \cup (M' \setminus M) contains a path or cycle that is MM-augmenting, i.e. an MM-alternating path with both endpoints MM-exposed. More specifically, we use the following direction, which is all the main proof needs: if MM is a matching in GG that does not saturate XX, and there is no MM-augmenting path starting at some MM-exposed vertex x0∈Xx_0 \in X, then in fact no matching can saturate XX using more edges through the reachable structure from x0x_0 — this is made precise inside the main proof via the alternating-reachability set.

Proof

We prove the two directions of the main theorem separately. The forward direction (necessity) is short; the reverse direction (sufficiency) is the substantial part and uses the augmenting path algorithm, an inductive construction.

Necessity. Suppose MM is a matching saturating XX. Let S⊆XS \subseteq X be arbitrary. Since MM saturates SS, the map x↦M(x)x \mapsto M(x) (sending each x∈Sx \in S to its unique MM-partner) is an injection from SS into YY, and moreover every M(x)M(x) for x∈Sx \in S lies in N(S)N(S) because xM(x)∈Ex M(x) \in E. Hence N(S)N(S) contains an injective image of SS, so ∣N(S)∣≥∣S∣|N(S)| \geq |S|. As SS was arbitrary this is Hall's condition. This direction uses only the definition of matching and injection counting; no further machinery is needed.

Sufficiency. Assume Hall's condition holds for every S⊆XS \subseteq X. We construct, by induction on k=0,1,…,∣X∣k = 0, 1, \dots, |X|, a matching MkM_k saturating kk specified vertices of XX, until k=∣X∣k = |X|. Formally, we prove the following claim by strong induction on the number of exposed vertices in XX: > Claim. If MM is a matching in GG that does not saturate all of XX, and Hall's condition holds for GG, then there exists a matching M′M' with ∣M′∣=∣M∣+1|M'| = |M| + 1. Granting the claim, start from M0=∅M_0 = \varnothing and repeatedly apply the claim; the number of MM-exposed vertices in XX strictly decreases (by exactly one) at each application, since ∣M∣|M| increases by exactly 11 and each edge of a matching saturates exactly one new vertex of XX compared to before (we verify this inside the claim's proof). Since XX is finite, after at most ∣X∣|X| applications we reach a matching saturating all of XX. This finite induction is well-founded because ∣X∣−∣M∣|X| - |M| (a non-negative integer, the number of exposed vertices of XX) strictly decreases with each step and cannot go below 00.

Proof of Claim. Let MM be a matching not saturating XX, and fix an MM-exposed vertex x0∈Xx_0 \in X. Define the alternating reachability sets: let R⊆X∪YR \subseteq X \cup Y be the set of all vertices reachable from x0x_0 by MM-alternating paths (paths starting at x0x_0 whose edges alternate between non-matching and matching edges, starting with a non-matching edge; x0x_0 itself is included in RR). Let RX=R∩XR_X = R \cap X and RY=R∩YR_Y = R \cap Y. Sub-claim (a): every vertex of RYR_Y is MM-saturated, EXCEPT possibly none — i.e. either some y∈RYy \in R_Y is exposed (giving an augmenting path immediately), or all of RYR_Y is saturated. We split into two cases. Case 1: some y∈RYy \in R_Y is MM-exposed. Then the alternating path from x0x_0 to yy used to reach yy is an MM-alternating path from the exposed vertex x0x_0 to the exposed vertex yy, i.e. it is MM-augmenting (its first edge is non-matching since x0x_0 has no matching edge to start with, and it must end on a non-matching edge into yy since alternation forces this and yy has no matching edge to close with). Call this path PP. Define M′=M△E(P)M' = M \triangle E(P) (remove the matching edges of PP from MM, add the non-matching edges of PP). We verify M′M' is a matching: every vertex not on PP has the same matching status as before. Every internal vertex of PP was matched by an edge of PP under MM and remains matched by the adjacent edge of PP under M′M' (alternation guarantees each internal vertex is incident to exactly one matching and one non-matching edge of PP, and these swap roles). The two endpoints x0,yx_0, y were MM-exposed and become M′M'-saturated (each newly incident to the edge of PP touching it, which was non-matching in MM and is matching in M′M'). No vertex is incident to two edges of M′M' because PP is a simple path (bipartite graphs have no odd cycles, and more simply, a path visits each vertex once) and M∖MM \setminus M-edges-of-PP retains the matching property outside PP. Hence M′M' is a matching, and ∣M′∣=∣M∣+1|M'| = |M| + 1 since PP has one more non-matching edge than matching edge (odd length, alternating, starting and ending with non-matching edges). This proves the claim in Case 1. Case 2: every y∈RYy \in R_Y is MM-saturated. We show this case is impossible under Hall's condition, which will complete the proof (Case 1 must occur). First, observe: for every y∈RYy \in R_Y, since yy is MM-saturated, its matching partner M(y)∈XM(y) \in X is also in RR (hence in RXR_X) — because the alternating path reaching yy can be extended by the matching edge yM(y)y M(y) to reach M(y)M(y), and this extended path is still alternating (it ends non-matching-then-matching). So the map y↦M(y)y \mapsto M(y) sends RYR_Y into RX∖{x0}R_X \setminus \{x_0\}, and it is injective (each x∈Xx \in X has at most one matching partner). Thus

∣RY∣≤∣RX∣−1.(∗)|R_Y| \leq |R_X| - 1. \tag{$\ast$}

(The −1-1 because x0∈RXx_0 \in R_X is not the image of any yy, as x0x_0 is exposed and has no matching partner.) Second, we show N(RX)⊆RYN(R_X) \subseteq R_Y. Indeed if x∈RXx \in R_X and xy∈Exy \in E for some y∈Yy \in Y, then either xyxy is already an edge of the alternating path reaching xx (so y∈RYy \in R_Y trivially if the path continues), or, regardless of the path used, we may extend the alternating path reaching xx by traversing the non-matching edge xyxy to reach yy: if the path reaching xx ended on a matching edge (which it must, unless x=x0x = x_0), then appending the non-matching edge xyxy keeps alternation valid, so y∈RYy \in R_Y. If x=x0x = x_0, the same works directly since x0x_0's only outgoing alternating-path edges are non-matching ones by definition of alternation starting non-matching. In every case y∈Ry \in R, and since y∈Yy \in Y, y∈RYy \in R_Y. Hence N(RX)⊆RYN(R_X) \subseteq R_Y, and combined with the trivial containment RY⊆N(RX)R_Y \subseteq N(R_X) (every y∈RY∖{y \in R_Y \setminus \{possibly reached only via matching edges}\}... in fact every y∈RYy \in R_Y is reached via a non-matching edge from some x∈RXx \in R_X by definition of the alternating path, so RY⊆N(RX)R_Y \subseteq N(R_X) as well), we get

N(RX)=RY.N(R_X) = R_Y.

Now apply Hall's condition to the set RX⊆XR_X \subseteq X:

∣N(RX)∣≥∣RX∣  ⟹  ∣RY∣≥∣RX∣.|N(R_X)| \geq |R_X| \implies |R_Y| \geq |R_X|.

But this directly contradicts (∗)(\ast), which says ∣RY∣≤∣RX∣−1<∣RX∣|R_Y| \leq |R_X| - 1 < |R_X|. This contradiction shows Case 2 cannot occur. Therefore Case 1 must occur: an augmenting path exists from x0x_0, and we constructed M′M' with ∣M′∣=∣M∣+1|M'| = |M|+1. This proves the Claim. ■\blacksquare

Conclusion. By the Claim and the finite induction described above, starting from the empty matching and repeatedly augmenting, we obtain after finitely many steps a matching MM that saturates all of XX (the process must terminate at a matching with no exposed vertex in XX, since otherwise the Claim would let us continue, contradicting termination — and it does terminate since ∣M∣|M| is a strictly increasing sequence of integers bounded above by min⁡(∣X∣,∣Y∣)\min(|X|,|Y|)). This matching witnesses the existence required by the theorem. ■\blacksquare

∎
CorollaryDeficiency (Ore's) version

Let G=(X∪Y,E)G = (X \cup Y, E) be bipartite with X,YX, Y finite. Define the deficiency

def(G)=max⁡S⊆X(∣S∣−∣N(S)∣)≥0\mathrm{def}(G) = \max_{S \subseteq X} \big( |S| - |N(S)| \big) \geq 0

(the maximum is ≥0\geq 0 since S=∅S = \varnothing gives 00). Then the maximum size of a matching in GG equals

∣X∣−def(G).|X| - \mathrm{def}(G).
Proof

We prove both inequalities.

(≤\leq): Let MM be any matching, and let S∗⊆XS^* \subseteq X achieve the maximum defining def(G)\mathrm{def}(G). The vertices of S∗S^* that are MM-saturated are matched into distinct vertices of N(S∗)N(S^*) (matching partners of vertices in S∗S^* lie in N(S∗)N(S^*) by definition, and are distinct since MM is a matching), so the number of MM-saturated vertices in S∗S^* is at most ∣N(S∗)∣|N(S^*)|. Hence the number of MM-exposed vertices in S∗S^* is at least ∣S∗∣−∣N(S∗)∣=def(G)|S^*| - |N(S^*)| = \mathrm{def}(G). Since exposed vertices in S∗⊆XS^* \subseteq X contribute to exposed vertices in XX overall,

∣X∣−∣M∣  ≥  (number of M-exposed vertices in X)  ≥  def(G),|X| - |M| \;\geq\; \text{(number of }M\text{-exposed vertices in } X) \;\geq\; \mathrm{def}(G),

using that ∣M∣≤∣X∣|M| \le |X| many vertices of XX are saturated so exactly ∣X∣−∣M∣|X|-|M| are exposed (each matching edge saturates exactly one vertex of XX, since GG is bipartite and MM's edges each have exactly one endpoint in XX). Thus ∣M∣≤∣X∣−def(G)|M| \leq |X| - \mathrm{def}(G) for every matching MM, so the maximum matching size is ≤∣X∣−def(G)\leq |X| - \mathrm{def}(G).

(≥\geq): We exhibit a matching of size ∣X∣−def(G)|X| - \mathrm{def}(G). Add a set ZZ of def(G)\mathrm{def}(G) new auxiliary vertices to YY, each joined to every vertex of XX, forming an augmented bipartite graph G+=(X∪(Y∪Z),E∪(X×Z))G^+ = (X \cup (Y \cup Z), E \cup (X \times Z)). We check G+G^+ satisfies Hall's condition relative to XX: for any S⊆XS \subseteq X,

NG+(S)=NG(S)∪Z(since every x∈S is joined to all of Z),N_{G^+}(S) = N_G(S) \cup Z \quad\text{(since every } x \in S \text{ is joined to all of } Z\text{)},

so ∣NG+(S)∣≥∣NG(S)∣+∣Z∣|N_{G^+}(S)| \geq |N_G(S)| + |Z| if S≠∅S \neq \varnothing and Z⊆NG+(S)Z \subseteq N_{G^+}(S) regardless (as long as S≠∅S \ne \varnothing; the empty set is trivial). Precisely, ∣NG+(S)∣=∣NG(S)∪Z∣=∣NG(S)∣+∣Z∣|N_{G^+}(S)| = |N_G(S) \cup Z| = |N_G(S)| + |Z| since ZZ is disjoint from YY by construction. We need ∣NG(S)∣+def(G)≥∣S∣|N_G(S)| + \mathrm{def}(G) \geq |S|, i.e. ∣S∣−∣NG(S)∣≤def(G)|S| - |N_G(S)| \leq \mathrm{def}(G), which holds for every S⊆XS \subseteq X by definition of def(G)\mathrm{def}(G) as the maximum of exactly this quantity. So G+G^+ satisfies Hall's condition. By Hall's Marriage Theorem (the theorem just proved) applied to G+G^+, there is a matching M+M^+ in G+G^+ saturating all of XX; ∣M+∣=∣X∣|M^+| = |X|. At most def(G)\mathrm{def}(G) edges of M+M^+ use a vertex of ZZ (since ∣Z∣=def(G)|Z| = \mathrm{def}(G) and ZZ-vertices can each be used at most once). Discard those edges; the remaining edges lie in EE (the original graph) and form a matching MM in GG with

∣M∣≥∣X∣−def(G).|M| \geq |X| - \mathrm{def}(G).

Combining both inequalities gives equality: the maximum matching size in GG is exactly ∣X∣−def(G)|X| - \mathrm{def}(G). ■\blacksquare

∎
CorollaryPerfect matchings in kk-regular bipartite graphs

If G=(X∪Y,E)G = (X \cup Y, E) is bipartite and kk-regular for some integer k≥1k \geq 1 (every vertex has degree exactly kk), then ∣X∣=∣Y∣|X| = |Y| and GG has a perfect matching.

Proof

Counting edges from each side: k∣X∣=∣E∣=k∣Y∣k|X| = |E| = k|Y| (every edge is counted once from its XX-endpoint's degree sum, and once from its YY-endpoint's degree sum), so ∣X∣=∣Y∣|X| = |Y| since k≥1k \geq 1. We check Hall's condition for XX. Fix S⊆XS \subseteq X, and count the edges between SS and N(S)N(S) in two ways. Every edge from SS lands in N(S)N(S) by definition of neighborhood, so the number of edges incident to SS is exactly k∣S∣k|S| (each vertex of SS has degree kk, and bipartiteness means all its edges go to YY, hence to N(S)N(S)). On the other hand, the number of edges incident to N(S)N(S) that land in SS is at most the total degree of N(S)N(S), namely k∣N(S)∣k|N(S)| (each vertex of N(S)N(S) has degree exactly kk, and edges into SS are a subset of all its edges). Since every edge between SS and N(S)N(S) is counted in both quantities,

k∣S∣  ≤  k∣N(S)∣,k|S| \;\leq\; k|N(S)|,

so ∣S∣≤∣N(S)∣|S| \leq |N(S)|. This holds for every S⊆XS \subseteq X, so Hall's condition holds. By Hall's Marriage Theorem, GG has a matching MM saturating XX; since ∣X∣=∣Y∣|X| = |Y| and MM saturates XX, MM has ∣X∣=∣Y∣|X| = |Y| edges, so MM also saturates YY (each of the ∣Y∣|Y| vertices of YY can absorb at most one matching edge, and there are exactly ∣Y∣|Y| edges hitting ∣Y∣|Y| vertices of YY with no repeats since MM is a matching, forcing every vertex of YY to be hit). Hence MM is perfect. ■\blacksquare

∎

Worked examples

Example 1 (Hall's condition verified directly, asymmetric sizes). Let X={x1,x2,x3,x4}X = \{x_1, x_2, x_3, x_4\} and Y={y1,y2,y3,y4,y5}Y = \{y_1, y_2, y_3, y_4, y_5\} with edges

x1:{y1,y2},x2:{y2,y3},x3:{y1,y3,y4},x4:{y4,y5}.x_1: \{y_1, y_2\}, \quad x_2: \{y_2, y_3\}, \quad x_3: \{y_1, y_3, y_4\}, \quad x_4: \{y_4, y_5\}.

We check Hall's condition for all (41)+(42)+(43)+(44)=15\binom{4}{1} + \binom{4}{2} + \binom{4}{3} + \binom{4}{4} = 15 nonempty subsets, but it suffices to check the "tight" and structurally interesting ones since singletons are automatic (each xix_i has degree ≥1\geq 1... actually degree ≥2\geq 2 here, so singletons trivially satisfy ∣N({xi})∣≥1=∣S∣|N(\{x_i\})|\ge 1 = |S|; more precisely each has degree 22 or 3≥13 \geq 1). Check pairs: N({x1,x2})={y1,y2,y3}N(\{x_1,x_2\}) = \{y_1,y_2,y_3\}, size 3≥23 \geq 2. N({x1,x3})={y1,y2,y3,y4}N(\{x_1,x_3\}) = \{y_1,y_2,y_3,y_4\}, size 4≥24 \geq 2. N({x1,x4})={y1,y2,y4,y5}N(\{x_1,x_4\}) = \{y_1,y_2,y_4,y_5\}, size 44. N({x2,x3})={y1,y2,y3,y4}N(\{x_2,x_3\}) = \{y_1,y_2,y_3,y_4\}, size 44. N({x2,x4})={y2,y3,y4,y5}N(\{x_2,x_4\}) = \{y_2,y_3,y_4,y_5\}, size 44. N({x3,x4})={y1,y3,y4,y5}N(\{x_3,x_4\}) = \{y_1,y_3,y_4,y_5\}, size 44. Check triples: N({x1,x2,x3})={y1,y2,y3,y4}N(\{x_1,x_2,x_3\}) = \{y_1,y_2,y_3,y_4\}, size 4≥34 \geq 3. N({x1,x2,x4})={y1,y2,y3,y4,y5}N(\{x_1,x_2,x_4\}) = \{y_1,y_2,y_3,y_4,y_5\}, size 55. N({x1,x3,x4})={y1,y2,y3,y4,y5}N(\{x_1,x_3,x_4\}) = \{y_1,y_2,y_3,y_4,y_5\}, size 55. N({x2,x3,x4})={y1,y2,y3,y4,y5}N(\{x_2,x_3,x_4\}) = \{y_1,y_2,y_3,y_4,y_5\}, size 55. Full set: N(X)={y1,…,y5}N(X) = \{y_1,\dots,y_5\}, size 5≥45 \geq 4. Every inequality holds, most strictly, with {x1,x2,x3}\{x_1,x_2,x_3\} giving the tightest ratio (44 neighbors for 33 vertices — still slack). Hall's condition holds, so a matching saturating XX exists. Explicitly: x1y1x_1 y_1, x2y2x_2 y_2 or y3y_3, x3y3x_3 y_3 or leftover, x4y4x_4 y_4 or y5y_5. Concretely take M={x1y1, x2y2, x3y3, x4y4}M = \{x_1 y_1,\ x_2 y_2,\ x_3 y_3,\ x_4 y_4\}: check no shared vertices — y1,y2,y3,y4y_1,y_2,y_3,y_4 are all distinct and each edge is present in GG (x1y1x_1y_1: yes; x2y2x_2y_2: yes; x3y3x_3y_3: yes; x4y4x_4y_4: yes). This MM is a valid matching saturating all of XX, confirming the theorem's conclusion constructively.

Example 2 (running the augmenting path algorithm to find a matching, and diagnosing a deficiency). Let X={x1,x2,x3,x4,x5}X = \{x_1,x_2,x_3,x_4,x_5\}, Y={y1,y2,y3,y4}Y=\{y_1,y_2,y_3,y_4\}, with edges

x1:{y1},x2:{y1,y2},x3:{y2,y3},x4:{y1,y3},x5:{y1,y2,y3}.x_1:\{y_1\},\quad x_2:\{y_1,y_2\},\quad x_3:\{y_2,y_3\},\quad x_4:\{y_1,y_3\},\quad x_5:\{y_1,y_2,y_3\}.

Note ∣X∣=5>4=∣Y∣|X| = 5 > 4 = |Y|, so no matching can saturate XX (Hall's condition already fails for S=XS = X: ∣N(X)∣=∣{y1,y2,y3}∣=3<5|N(X)| = |\{y_1,y_2,y_3\}| = 3 < 5, since y4y_4 has no neighbor among these edges — indeed y4y_4 is isolated). We compute the actual maximum matching size via augmenting paths and cross-check with the deficiency formula. Step 0. M0=∅M_0 = \varnothing. Step 1. Take exposed x1x_1. Trivial augmenting path x1y1x_1 y_1 (both exposed, length 11). Update: M1={x1y1}M_1 = \{x_1 y_1\}. Step 2. Take exposed x2x_2. Trivial path x2y2x_2 y_2 (both exposed). Update: M2={x1y1,x2y2}M_2 = \{x_1y_1, x_2y_2\}. Step 3. Take exposed x3x_3. Trivial path x3y3x_3 y_3 (both exposed). Update: M3={x1y1,x2y2,x3y3}M_3 = \{x_1y_1, x_2y_2, x_3y_3\}. Step 4. Take exposed x4x_4. Neighbors of x4x_4: y1y_1 (matched to x1x_1), y3y_3 (matched to x3x_3). Both neighbors matched, so we must extend the alternating search. From x4x_4, non-matching edge to y1y_1; y1y_1's matching edge goes to x1x_1; from x1x_1, only neighbor is y1y_1 (already visited), dead end on this branch. Alternatively from x4x_4, non-matching edge to y3y_3; y3y_3's matching edge goes to x3x_3; from x3x_3, neighbors are y2y_2 (matched to x2x_2) and y3y_3 (visited). Non-matching edge x3y2x_3 y_2; y2y_2's matching edge goes to x2x_2; from x2x_2, neighbors are y1y_1 (visited), y2y_2 (visited). Dead end. The reachability set from x4x_4 is R={x4,y1,x1,y3,x3,y2,x2}R = \{x_4, y_1, x_1, y_3, x_3, y_2, x_2\}, i.e. RX={x1,x2,x3,x4}R_X = \{x_1,x_2,x_3,x_4\}, RY={y1,y2,y3}R_Y=\{y_1,y_2,y_3\}, and every vertex in RYR_Y is matched — no augmenting path exists. This is exactly Case 2 of the proof, and it certifies a Hall violation: N(RX)={y1,y2,y3}=RYN(R_X) = \{y_1,y_2,y_3\} = R_Y has size 3<4=∣RX∣3 < 4 = |R_X|, confirming the obstruction directly. Step 5. Take exposed x5x_5: same reachable set structure (its neighbors are also {y1,y2,y3}\{y_1,y_2,y_3\}, all matched, and the alternating search again closes without reaching an exposed yy), so no augmentation is possible from x5x_5 either. The algorithm terminates with M3M_3, a matching of size 33. Cross-check via the deficiency formula: taking S={x1,x2,x3,x4,x5}=XS = \{x_1,x_2,x_3,x_4,x_5\} = X, N(S)={y1,y2,y3}N(S) = \{y_1,y_2,y_3\} (since y4y_4 is isolated), so ∣S∣−∣N(S)∣=5−3=2|S| - |N(S)| = 5 - 3 = 2. One checks no subset gives a larger deficiency (any proper subset omits at least one xix_i but the neighbor set can shrink too; direct check of S={x1,x2,x4,x5}S=\{x_1,x_2,x_4,x_5\} gives N(S)={y1,y2,y3}N(S)=\{y_1,y_2,y_3\}, deficiency 4−3=14-3=1, smaller). So def(G)=2\mathrm{def}(G) = 2, and the formula predicts maximum matching size ∣X∣−def(G)=5−2=3|X| - \mathrm{def}(G) = 5 - 2 = 3, matching exactly what the algorithm found.

CounterexampleWhy finiteness (or an analogous safeguard) cannot simply be dropped

Hall's theorem as stated requires XX and YY to be finite. If we allow XX to be countably infinite, the direct analogue of the theorem (that Hall's condition on all finite subsets of XX implies a matching saturating XX) can actually still be salvaged with extra care (a version of Hall's theorem holds for locally finite infinite bipartite graphs, by a compactness argument), but a naive removal of finiteness assumptions elsewhere in the argument breaks down completely. We exhibit the classical failure when YY is allowed to make the "trivial" containment argument fail: consider

X={x1,x2,x3,… },Y={y0}∪{y1,y2,y3,… },X = \{x_1, x_2, x_3, \dots\}, \qquad Y = \{y_0\} \cup \{y_1, y_2, y_3, \dots\},

with edges xiy0x_i y_0 for every ii, and xiyix_i y_i for every i≥1i \geq 1 additionally. Here every finite S⊆XS \subseteq X has N(S)={y0}∪{yi:xi∈S}N(S) = \{y_0\} \cup \{y_i : x_i \in S\}, so ∣N(S)∣=∣S∣+1≥∣S∣|N(S)| = |S| + 1 \geq |S|: Hall's condition holds for every finite subset. And indeed here a matching saturating XX does exist (xi↦yix_i \mapsto y_i for each ii), so this particular graph is not a counterexample to existence — it illustrates instead why the proof's inductive machinery (finite induction terminating after ∣X∣|X| steps) cannot be used verbatim: there is no finite bound on the number of augmentation steps, and the argument "the process terminates because ∣X∣−∣M∣|X|-|M| is a decreasing non-negative integer" requires ∣X∣|X| finite to conclude termination in finitely many steps at all. Without finiteness, the entire inductive proof structure — which explicitly uses "finite induction" bounded by ∣X∣|X| — no longer applies, and a genuine construction of the required matching needs a fundamentally different tool (e.g. a compactness or Zorn's-lemma argument on the space of partial matchings). This shows finiteness is not merely convenient bookkeeping: it is the load-bearing hypothesis that makes the induction in the proof well-founded and guarantees termination in a bounded number of steps.

Scope, edge cases & common traps

SituationWhat happens
∣X∣>∣Y∣|X| > |Y|Hall's condition automatically fails for S=XS=X (since ∣N(X)∣≤∣Y∣<∣X∣|N(X)| \le |Y| < |X|); no matching saturates XX
∣X∣=∣Y∣|X| = |Y|, Hall's condition holdsMatching saturating XX is automatically perfect (saturates YY too, by a counting argument as in the regular case)
Hall's condition checked only for singletonsInsufficient — must hold for every subset, not just small ones; larger subsets can still fail even if all singletons pass
Graph not bipartiteHall's theorem does not directly apply; the general (Tutte–Berge) matching theory is needed instead
Checking Hall's condition by brute forceRequires checking up to 2∣X∣2^{|X|} subsets in the worst case; efficient certification instead uses the augmenting-path algorithm's failure to produce a violating set directly (as in Example 2)

The mathematician behind it

Origins · 1 minPhilip Hall and how this was discovered
PH
Philip Hall
1904–1982 · British algebraist and group theorist, Cambridge and later a professor at Cambridge

Philip Hall was primarily an algebraist, renowned for foundational work in group theory (Hall subgroups, the Hall–Petrescu formula, and Hall's theorem on solvable groups), but his 1935 paper "On Representatives of Subsets" introduced the marriage condition in the combinatorial form now bearing his name, originally phrased in terms of "systems of distinct representatives" for a family of finite sets.

History
- 1935: Philip Hall publishes "On Representatives of Subsets," proving what is now Hall's Marriage Theorem, phrased as a condition for systems of distinct representatives.
- 1931: Dénes Kőnig and Jenő Egerváry independently establish closely related min-max results on bipartite graphs (König's theorem on matchings and vertex covers), predating and interlocking with Hall's work.
- 1955: Marshall Hall Jr. (no relation) extends the theorem to infinite systems under suitable finiteness conditions, addressing exactly the subtlety flagged in the counterexample above.
- 1957: The augmenting path method is formalized algorithmically, feeding directly into the development of network flow theory by Ford and Fulkerson.
- 1965: Jack Edmonds generalizes matching theory to general (non-bipartite) graphs, proving the Tutte–Berge formula constructively via the blossom algorithm, extending the augmenting-path idea beyond the bipartite setting.
What exactly does "saturate" mean, and how is it different from "perfect matching"?

A matching MM saturates a vertex vv if vv is an endpoint of some edge in MM; it saturates a set if every vertex in that set is individually saturated. A perfect matching saturates every vertex in the whole graph, both XX and YY. Hall's theorem is about saturating just one side, XX — a weaker requirement when ∣X∣<∣Y∣|X| < |Y|, since leftover vertices of YY are allowed to remain exposed. When ∣X∣=∣Y∣|X| = |Y|, saturating XX automatically forces saturating YY too (a counting argument: the matching has ∣X∣|X| edges, each hitting a distinct vertex of YY, and there are exactly ∣Y∣=∣X∣|Y|=|X| such vertices), so in that special case "saturates XX" and "perfect" coincide.

Is Hall's condition checked on subsets of XX or of YY, and does it matter which side?

It matters, and the statement must specify a side. Hall's theorem as given tests subsets S⊆XS \subseteq X against N(S)⊆YN(S) \subseteq Y, and its conclusion is existence of a matching saturating XX. The analogous statement for YY (checking subsets T⊆YT \subseteq Y against N(T)⊆XN(T) \subseteq X) is a logically independent theorem about saturating YY instead. Both can hold simultaneously (guaranteeing a perfect matching when ∣X∣=∣Y∣|X|=|Y|), one can hold without the other, or neither may hold. Always be explicit about which side's condition is being verified and which side's saturation is being claimed.

How does the augmenting path algorithm relate to actual computer algorithms for matching?

The proof's construction — repeatedly finding an augmenting path from an exposed vertex and flipping the matching along it — is essentially the Hopcroft–Karp / Hungarian algorithm's core subroutine, executed one augmentation at a time. A naive implementation runs a breadth-first search from each exposed vertex to find an augmenting path, giving O(∣X∣⋅∣E∣)O(|X|\cdot|E|) time overall; smarter implementations find several vertex-disjoint augmenting paths per phase, achieving O(∣X∣⋅∣E∣)O(\sqrt{|X|}\cdot|E|) total time. The mathematical content — that failure to find an augmenting path certifies a Hall-violating (equivalently, minimum vertex cover) set — is exactly what makes these algorithms correct and terminating, not merely heuristic.

Does Hall's theorem give a unique matching, or just existence?

Only existence, and typically far from uniqueness. Many different matchings can saturate XX whenever the neighborhoods overlap generously; Example 1 above admits several valid saturating matchings besides the one exhibited (for instance swapping x2x_2's and x3x_3's assigned neighbors where alternatives exist). Counting the number of perfect matchings is a separate and generally much harder problem, related to the permanent of the bipartite adjacency matrix, which is #P-hard to compute exactly in general — a sharp contrast with the polynomial-time decidability of mere existence via Hall's condition or augmenting paths.

What happens if the bipartite graph is disconnected?

Hall's condition and the theorem apply without modification; disconnection causes no special behavior because neighborhoods N(S)N(S) are computed purely from the edge set as given, and a disconnected component with too few neighbors on one side will simply show up as a genuine Hall violation restricted to that component. Equivalently, one may check Hall's condition component by component: the whole graph satisfies Hall's condition (relative to XX) if and only if each connected component does relative to its own XX-part, since neighborhoods never cross components and any violating subset must lie within a single component.

How does Hall's theorem relate to Latin squares and Latin rectangle completion?

An r×nr \times n Latin rectangle (using symbols 1,…,n1,\ldots,n, r≤nr \le n, no symbol repeated in any row or column) can be extended to an (r+1)×n(r+1)\times n Latin rectangle if and only if a suitable bipartite matching exists: let XX be the nn columns and YY the nn symbols, with column cc adjacent to symbol ss if ss does not already appear in column cc. One shows this bipartite graph is regular enough (each column misses exactly n−rn-r symbols, and by a counting argument each symbol is missing from exactly n−rn - r columns) that Hall's condition holds, guaranteeing a perfect matching, which is precisely the next row extending the rectangle. Iterating shows every Latin rectangle extends all the way to a full Latin square.

Why is the deficiency version stated as an equality rather than just an inequality?

Because both directions are provable and both are needed for applications: the inequality ∣M∣≤∣X∣−def(G)|M| \le |X| - \mathrm{def}(G) shows deficiency is a genuine obstruction (an upper bound witnessed by a single bad subset), while the reverse inequality shows this obstruction is tight — no subtler global reason can force the maximum matching smaller than what the worst subset already predicts. This equality is a min-max theorem in miniature: the minimum over "bad subsets" of how much they overshoot their neighborhoods exactly equals the maximum shortfall of any matching from perfection, foreshadowing the identical min-max flavor of König's Theorem and Vertex Covers and, more generally, max-flow min-cut duality.

Before this

Where this leads