Hall's marriage theorem

Theorem

Hall's marriage theorem

T-110Home MU-307Threads structure · number

Statement

Let \(G = (X \cup Y, E)\) be a finite bipartite graph with vertex classes \(X\) and \(Y\) and edge set \(E \subseteq X \times Y\). For \(S \subseteq X\) write \(N(S) = \{ y \in Y : \exists x \in S,\ xy \in E \}\) for the set of neighbours of \(S\). Then \(G\) admits a matching that saturates \(X\) (an injection \(f : X \to Y\) with \(xf(x) \in E\) for every \(x \in X\)) if and only if \[ |N(S)| \geq |S| \quad \text{for every } S \subseteq X. \] The condition on the right is called Hall's condition, and a family of sets satisfying it (viewing each \(x \in X\) as indexing the set \(N(\{x\})\)) is said to admit a system of distinct representatives.

Why it matters

Hall's theorem is the founding existence theorem of matching theory: it converts a question about a global combinatorial object (an injective assignment) into a question that can, in principle, be checked set by set. It is the bipartite ancestor of a whole family of "local condition implies global structure" theorems — König's theorem, the max-flow min-cut theorem, Menger's theorem, and Tutte's theorem for general graphs are all cousins, and several are proved by reducing to Hall or by the same augmenting-path idea.

Beyond graph theory the theorem is the standard tool for constructing systems of distinct representatives (SDRs): given a family of finite sets \(A_1,\dots,A_n\), Hall's condition says exactly when one can choose an element \(a_i \in A_i\) for each \(i\) with all the \(a_i\) distinct. This phrasing is the one used most often in applications — assigning committees to rooms, jobs to workers, course sections to time slots.

Hypotheses

\(G\) is bipartite with the fixed bipartition \(X \cup Y\). Without a bipartition the statement is not even well posed — "matching saturating \(X\)" requires a distinguished side. For general (non-bipartite) graphs the correct existence criterion is Tutte's theorem, phrased via odd components, and Hall's vertex-counting condition is neither necessary nor sufficient there; e.g. a triangle \(K_3\) has no bipartition but has a near-perfect matching, and Hall's neighbourhood inequality has no meaning without one. \(X\) and \(Y\) (hence \(E\)) are finite. For infinite \(X\) the naive statement fails: let \(X = \mathbb{N}\), and let \(x_0\) be joined to every \(y \in Y = \mathbb{N}\), while each \(x_{n}\) for \(n \geq 1\) is joined only to \(y_n\). Hall's condition holds for every finite \(S\subseteq X\) (in fact for every \(S\)), yet no matching saturates \(X\): all of \(x_1,x_2,\dots\) must use \(y_1,y_2,\dots\) respectively (forced, since those are their only neighbours), leaving no neighbour of \(x_0\) unused. The correct infinite generalisation (M. Hall Jr.'s theorem) needs an extra local-finiteness condition on the \(A_i\). The condition is checked for every subset \(S \subseteq X\), not just singletons or "obvious" sets. Checking only singletons gives \(|N(\{x\})|\geq 1\), i.e. "no isolated vertex in \(X\)" — far too weak. Example: \(X=\{x_1,x_2\}\), \(Y=\{y_1\}\), both \(x_1,x_2\) joined only to \(y_1\). Every singleton is fine, but \(S=\{x_1,x_2\}\) gives \(|N(S)|=1 \lt 2\), and indeed no matching saturates \(X\).

Proof

We prove the non-trivial direction (Hall's condition \(\Rightarrow\) a saturating matching) by strong induction on \(|X|\); the converse is immediate. We follow the classical argument via "critical sets", which is self-contained and avoids invoking network flow machinery, though we remark at the end how it specialises the max-flow min-cut theorem.

(\(\Leftarrow\), easy direction) If a matching \(f\) saturates \(X\), then for every \(S \subseteq X\), \(f(S) \subseteq N(S)\) and \(f|_S\) is injective, so \(|N(S)| \geq |f(S)| = |S|\).

Definition of a matching (injective, edge-respecting) and of \(N(S)\); \(f(S)\) is a set of \(|S|\) distinct elements of \(N(S)\) because \(f(x) \in N(\{x\}) \subseteq N(S)\) for \(x\in S\). A

(\(\Rightarrow\), base case) If \(|X| = 0\) the empty matching works trivially; if \(|X|=1\), say \(X=\{x\}\), Hall's condition with \(S=\{x\}\) gives \(N(\{x\}) \neq \varnothing\), so pick any \(y \in N(\{x\})\) and match \(x\) to \(y\).

Direct verification of the base case(s) of the induction. A

Now let \(|X| = n \geq 2\) and assume the theorem holds for all bipartite graphs with fewer than \(n\) vertices on the \(X\)-side. Call \(S \subsetneq X\) with \(S \neq \varnothing\) critical if \(|N(S)| = |S|\) (equality in Hall's condition).

Setting up the inductive hypothesis and a case split on whether equality is ever attained on a proper nonempty subset. B

\textbf{Case (i): no proper nonempty } S \textbf{ is critical.} Pick any \(x_0 \in X\); by Hall's condition \(N(\{x_0\}) \neq \varnothing\), so choose \(y_0 \in N(\{x_0\})\) and match \(x_0 \mapsto y_0\). Delete \(x_0\) and \(y_0\) to form \(G' = G - x_0 - y_0\) on \(X' = X\setminus\{x_0\}\), \(Y' = Y \setminus \{y_0\}\).

Construction; deleting one matched pair is the standard reduction step in induction on matchings. B

In \(G'\), for every nonempty \(S \subseteq X'\): \(N_{G'}(S) \geq N_G(S) \setminus \{y_0\}\), so \(|N_{G'}(S)| \geq |N_G(S)| - 1 \geq |S| - 1 + 1 = |S|\), using \(|N_G(S)| \geq |S|+1\) since \(S\) is not critical in \(G\) (it is a proper nonempty subset of \(X\), being a proper subset of \(X'\subsetneq X\)) and not equal to \(X\).

Removing one vertex from \(Y\) can shrink a neighbourhood by at most one; combined with the case hypothesis that Hall's inequality is strict on every proper nonempty \(S\subsetneq X\), the inequality survives the deletion. C

Hence \(G'\) satisfies Hall's condition and has \(|X'| = n-1 \lt n\); by the inductive hypothesis \(G'\) has a matching \(f'\) saturating \(X'\). Then \(f = f' \cup \{x_0 \mapsto y_0\}\) is a matching saturating \(X\).

Applying the inductive hypothesis and re-attaching the removed pair; the union is a valid matching since \(x_0,y_0\) were deleted from both sides so no conflicts arise. A

\textbf{Case (ii): some proper nonempty } S_0 \subsetneq X \textbf{ is critical, i.e. } |N(S_0)| = |S_0|. Split \(G\) into \(G_1 = G[S_0 \cup N(S_0)]\) (induced on \(S_0\) and its neighbourhood) and \(G_2 = G[(X\setminus S_0) \cup (Y \setminus N(S_0))]\).

Using a critical set to split the problem into two strictly smaller subproblems is the key idea of the proof. B

\(G_1\) satisfies Hall's condition (inherited directly from \(G\), since \(N_{G_1}(S)=N_G(S)\) for \(S\subseteq S_0\)), and \(|S_0| \lt |X|\) since \(S_0\) is proper; by induction \(G_1\) has a matching \(f_1\) saturating \(S_0\), using exactly the vertices \(N(S_0)\) on the \(Y\)-side (since \(|N(S_0)|=|S_0|\), \(f_1\) is a bijection \(S_0 \to N(S_0)\)).

Inductive hypothesis applied to \(G_1\), plus the counting fact that a saturating matching between sets of equal size is a bijection onto the smaller neighbourhood. B

For any \(T \subseteq X \setminus S_0\), \(N_{G_2}(T) = N_G(S_0 \cup T) \setminus N(S_0)\), so \(|N_{G_2}(T)| = |N_G(S_0\cup T)| - |N(S_0)| \geq |S_0 \cup T| - |S_0| = |S_0|+|T|-|S_0| = |T|\), using Hall's condition in \(G\) applied to \(S_0 \cup T\) and disjointness of \(S_0\) and \(T\).

Key computation: neighbours of \(T\) outside \(N(S_0)\) are exactly the "new" neighbours contributed when \(S_0\) is enlarged to \(S_0\cup T\), and Hall's condition for \(G\) at \(S_0\cup T\) bounds their number. C

So \(G_2\) satisfies Hall's condition and \(|X\setminus S_0| \lt |X|\) since \(S_0 \neq \varnothing\); by induction \(G_2\) has a matching \(f_2\) saturating \(X \setminus S_0\), landing entirely in \(Y \setminus N(S_0)\) by construction of \(G_2\).

Inductive hypothesis applied to \(G_2\). B

\(f = f_1 \cup f_2\) is well defined (disjoint domains \(S_0\), \(X\setminus S_0\)) and injective (disjoint ranges \(N(S_0)\), \(Y\setminus N(S_0)\)), and saturates \(X = S_0 \cup (X\setminus S_0)\). This completes the induction, and hence the proof of the theorem.

Gluing two matchings with disjoint domains and disjoint codomains yields a matching on the union; definition of matching. A

Remark: the same result follows from the max-flow min-cut theorem by orienting all edges from \(X\) to \(Y\), adding a source \(s\to X\) and \(Y \to t\) with unit capacities on \(s\)-edges and \(t\)-edges and capacity \(1\) (or \(\infty\)) on \(X\)-\(Y\) edges; a saturating matching exists iff the max flow equals \(|X|\), and a min \(s\)-\(t\) cut of size \(\lt |X|\) corresponds exactly to a violating set \(S\) with \(|N(S)| \lt |S|\).

Cited without full proof — the max-flow min-cut theorem (Ford–Fulkerson) is a separate, independently established result; noted here only to show the two proofs are not accidents of each other. C

Result

\(G=(X\cup Y,E)\) bipartite, finite. \(\exists\) matching saturating \(X\) \(\iff\) \(|N(S)|\geq|S|\ \ \forall S\subseteq X\)

Reading. You can pair off every element of \(X\) with a distinct partner in \(Y\) precisely when no group of elements of \(X\), taken together, is short of neighbours to go around.

Scope. Finite bipartite graphs (equivalently, finite set systems, for the SDR phrasing) only. Says nothing about matchings not saturating \(X\), about saturating \(Y\) as well (that needs the symmetric condition, or equality \(|X|=|Y|\) plus both conditions for a perfect matching), and does not extend verbatim to infinite \(X\) or to non-bipartite graphs.

Corollaries & converses

Regular bipartite graphs are perfectly matchable. If every vertex of \(G\) has the same degree \(k\geq 1\), counting edges between \(S\) and \(N(S)\) gives \(k|S| = e(S,N(S)) \leq k|N(S)|\), so \(|N(S)|\geq|S|\); Hall's condition holds automatically and, by symmetry (same argument from the \(Y\) side) and \(|X|=|Y|\) forced by double counting all edges, \(G\) has a perfect matching.
Defect version (Ore's extension). If Hall's condition fails, the maximum matching still saturates \(|X| - \max_{S\subseteq X}\left(|S|-|N(S)|\right)\) vertices of \(X\) — the theorem's proof extends to give the exact "deficiency" rather than just an existence dichotomy.
The condition is exactly necessary and sufficient — the theorem is a genuine iff, not a one-directional sufficient condition; Step 1 above establishes necessity independently of the inductive argument for sufficiency.
König's theorem (in bipartite graphs, max matching size \(=\) min vertex cover size) can be derived from the deficiency version, and conversely Hall's theorem is the special case of König's theorem where a vertex cover of size \(|X|\) is shown to be unavoidable exactly when Hall's condition fails.
Converse direction: as shown in Step 1, the neighbourhood condition is not merely sufficient but also necessary — there is no weaker "almost-Hall" condition that still guarantees a matching; the theorem is tight (see Fails without).

Fails without

Drop finiteness of \(X\): take \(X=\mathbb{N}\), \(x_0\) adjacent to all of \(Y=\mathbb{N}\), and \(x_n\) (\(n\geq1\)) adjacent only to \(y_n\). Hall's condition holds for every subset of \(X\) (finite or infinite), but no matching saturates \(X\): each \(x_n\), \(n\geq 1\), is forced to \(y_n\), exhausting all of \(Y\) and leaving \(x_0\) unmatched.
Drop bipartiteness: \(G=K_3\) (a triangle) on vertices \(\{a,b,c\}\) has no bipartition into an "\(X\)-side" — but forcing an artificial split, say \(X=\{a,b\}\), \(Y=\{c\}\) with all cross edges present (a legitimate bipartite subgraph, since \(ab\) is simply ignored), gives \(N(\{a,b\})=\{c\}\), so \(|N(S)|=1\lt 2=|S|\): Hall's condition fails and indeed no matching saturates \(\{a,b\}\) using only cross edges, even though the full graph \(K_3\) has a matching of size 1 covering two of the three vertices. This shows the bipartite structure is essential to how the neighbourhood condition is even phrased — for general graphs, matchability is governed by Tutte's odd-component condition instead.
Check the condition on a strict subfamily of subsets only (e.g. singletons, or only \(S=X\)): \(X=\{x_1,x_2,x_3\}\), \(Y=\{y_1,y_2\}\), with \(x_1\sim y_1\), \(x_2\sim y_1\), \(x_3\sim y_1,y_2\). Here \(|N(X)|=2\lt 3\) is already visible at \(S=X\), but subtler failures need intermediate sets: modify so \(x_3\sim y_2\) also fails, i.e. all three vertices only reach \(y_1\): then \(S=\{x_1,x_2\}\) alone gives \(|N(S)|=1\lt2\), a violation invisible if one checks only \(S=X\) or only singletons (each singleton has \(|N(\{x_i\})|=1\geq1\)).

Common errors

Checking Hall's condition only for singletons or only for \(S=X\), concluding "no isolated vertices and enough total neighbours" is sufficient — it is not; the condition must hold for every subset, and violations typically occur on intermediate-sized sets (see Fails without, third example).
Confusing \(N(S)\) (union of neighbourhoods) with \(\bigcap_{x\in S} N(\{x\})\) (common neighbours) — Hall's condition uses the union; using the intersection makes the condition far too strong and gives false negatives.
Believing Hall's theorem produces a perfect matching whenever \(|X|=|Y|\) — it only produces a matching saturating \(X\); a perfect matching additionally requires \(|X|=|Y|\) and saturation to automatically become mutual (which does follow when \(|X|=|Y|\) and \(f\) is a bijection onto \(Y\), but this must be checked, not assumed, when \(|X|\ne|Y|\)).
Applying the theorem to a non-bipartite graph by just picking an arbitrary "side" \(X\), as if any vertex partition would do — the theorem's hypotheses require the bipartition to be the graph's actual bipartition (all edges cross it); an artificial split on a non-bipartite graph discards edges and gives a meaningless answer (see Fails without, second example).
Forgetting the empty set: technically \(S=\varnothing\) gives \(|N(\varnothing)|=0\geq0\), trivially true, but students sometimes start their case-check at \(S=\varnothing\) and treat it as informative, or conversely forget that the "witnessing" violating set in a deficiency argument is always nonempty by construction.

Discussion

Hall's theorem was proved by Philip Hall in 1935, originally phrased in terms of systems of distinct representatives for a finite family of sets — the graph-theoretic dress it now wears is a later reformulation. The set-family phrasing is worth keeping in mind: given \(A_1,\dots,A_n\), form the bipartite graph with \(X=\{1,\dots,n\}\), \(Y=\bigcup_i A_i\), and \(i\sim y\) iff \(y\in A_i\); an SDR is precisely a matching saturating \(X\), and Hall's condition becomes "the union of any \(k\) of the \(A_i\) has size at least \(k\)".

The proof given here (via critical sets) is one of several standard routes; alternatives include an augmenting-path argument (start from any matching, show that if it fails to saturate \(X\) then Hall's condition is violated by tracing an alternating-path reachable set) and the flow-theoretic reduction sketched in Step 12. All three are secretly the same argument wearing different notation — the "critical set" \(S_0\) in the proof above is exactly the \(X\)-side of a minimum vertex cover / minimum cut in the other formulations, which is why the theorem sits at the intersection of König's theorem, Menger's theorem, and LP duality (Hall's condition is the combinatorial shadow of the integrality of the bipartite matching polytope).

A common misconception is that Hall's theorem is fundamentally an "existence by counting" result in the same spirit as pigeonhole; in fact it is considerably sharper, since pigeonhole-type counting only ever produces necessary conditions (as in Step 1), while the genuine content of the theorem is the converse direction — that the family of necessary conditions, infinite in principle but here finite since \(X\) is finite, is jointly sufficient. This "local-to-global" phenomenon, where checking exponentially many (\(2^{|X|}\)) local conditions certifies a single global object, recurs throughout combinatorial optimisation and is really a manifestation of strong LP duality for the (totally unimodular) bipartite matching polytope, not a combinatorial accident.

The theorem also generalises usefully: the "defect" form (deficiency Hall theorem, sometimes attributed to Ore) quantifies exactly how far short of saturation the maximum matching falls when the condition is violated, and the infinite version (M. Hall Jr., 1948) restores existence for infinite \(X\) provided every \(A_i\) (equivalently every \(N(\{x\})\)) is finite — precisely blocking the counterexample given in Hypotheses.

Worked examples

Committee assignment. Four committees \(C_1,C_2,C_3,C_4\) must each send one distinct representative from the pool of members below to a joint board; can this be done? \(C_1\) can supply \(\{a,b\}\); \(C_2\) can supply \(\{b,c\}\); \(C_3\) can supply \(\{a,b,c\}\); \(C_4\) can supply \(\{d\}\).

Recognising this as an SDR problem: \(X=\{C_1,C_2,C_3,C_4\}\), \(N(C_i)=\) that committee's eligible pool. A

Check Hall's condition on all \(2^4-1\) nonempty subsets; by inspection the only subsets at risk are ones avoiding \(d\), since \(C_4\) is disjoint from the rest. Worst case \(S=\{C_1,C_2,C_3\}\): \(N(S)=\{a,b\}\cup\{b,c\}\cup\{a,b,c\}=\{a,b,c\}\), \(|N(S)|=3=|S|\), OK (equality, critical but not violating). All other subsets of \(\{C_1,C_2,C_3\}\) also check out (e.g. any pair has \(|N(S)|\geq2\)), and adding \(C_4\) always adds the disjoint element \(d\), preserving the inequality.

Systematic Hall check — since \(\{C_1,C_2,C_3\}\) is critical (\(|N(S)|=|S|\)) this is the borderline case that determines feasibility; smaller subsets of it inherit slack. B

Hall's condition holds for every \(S\subseteq X\), so by the theorem an SDR exists. Explicitly: \(C_4\to d\), \(C_1 \to a\), \(C_2\to c\), \(C_3\to b\) (forced, since \(\{C_1,C_2,C_3\}\) is critical with \(N=\{a,b,c\}\), so this must be a bijection).

Applying the theorem (existence) then exhibiting a witness explicitly, using the bijection forced by criticality noted in Proof Step 8. A

SDR exists: \(C_1\to a,\ C_2\to c,\ C_3\to b,\ C_4\to d\)

Reading. All four committees can send distinct representatives simultaneously.

A scheduling problem. Five job applicants \(p_1,\dots,p_5\) must be assigned to five open roles \(r_1,\dots,r_5\), one each, respecting qualifications: \(p_1\to\{r_1,r_2\}\), \(p_2\to\{r_1,r_2\}\), \(p_3\to\{r_1,r_2\}\), \(p_4\to\{r_3\}\), \(p_5\to\{r_4,r_5\}\). Does a full assignment exist?

Set-up as a bipartite graph \(X=\{p_1,\dots,p_5\}\), edges to qualifying roles. A

Test \(S=\{p_1,p_2,p_3\}\): \(N(S)=\{r_1,r_2\}\), so \(|N(S)|=2 \lt 3=|S|\). Hall's condition already fails here.

Direct evaluation of the neighbourhood-counting inequality on the natural "suspicious" subset (three applicants competing for the same two roles). B

By the theorem (contrapositive of the \(\Leftarrow\) direction proved in Step 1 of Proof), no matching can saturate \(X\); in particular no full assignment of all five applicants to distinct roles exists. Quantitatively, the maximum matching saturates at most \(5-(3-2)=4\) of the five applicants (deficiency version), and this bound is attained: e.g. \(p_1\to r_1,\,p_2\to r_2,\,p_4\to r_3,\,p_5\to r_4\) leaves only \(p_3\) unassigned.

Applying the theorem's contrapositive for non-existence, then the deficiency refinement (cited in Corollaries) for the sharp quantitative statement, verified by exhibiting an explicit near-maximum matching. B

No full assignment; max matching covers exactly 4 of the 5 applicants

Reading. Three applicants chasing only two roles is an unavoidable bottleneck — one applicant must always be left out.

Problems

Let \(X=\{1,2,3\}\), \(Y=\{a,b,c,d\}\), with \(1\sim\{a,b\}\), \(2\sim\{b,c\}\), \(3\sim\{a,c,d\}\). Does a matching saturating \(X\) exist? Exhibit one or show Hall's condition fails.
Solution
Check all nonempty \(S\subseteq X\). Singletons: fine (each has \(\geq1\) neighbour). Pairs: \(N(\{1,2\})=\{a,b,c\}\), size 3 \(\geq\)2; \(N(\{1,3\})=\{a,b,c,d\}\), size4\(\geq\)2; \(N(\{2,3\})=\{a,b,c,d\}\), size4\(\geq\)2. Full set: \(N(\{1,2,3\})=\{a,b,c,d\}\), size4\(\geq\)3. Hall's condition holds throughout, so a saturating matching exists. Explicitly \(1\to a,\ 2\to b,\ 3\to c\) works (check: \(1\sim a\)✓, \(2\sim b\)✓, \(3\sim c\)✓, all distinct).
Let \(A_1=\{1,2\}\), \(A_2=\{1,2\}\), \(A_3=\{1,2\}\). Does this family have a system of distinct representatives? Explain using Hall's theorem.
Solution
Model as bipartite: \(X=\{A_1,A_2,A_3\}\), \(Y=\{1,2\}\), each \(A_i\) adjacent to both \(1\) and \(2\). Take \(S=X=\{A_1,A_2,A_3\}\): \(N(S)=\{1,2\}\), \(|N(S)|=2\lt3=|S|\). Hall's condition fails, so by the theorem no SDR exists — unsurprising, since three sets each of size 2 cannot supply three pairwise-distinct representatives (pigeonhole: only two distinct values \(1,2\) are ever available).
Prove: if \(G\) is bipartite with parts \(X,Y\), \(|X|=|Y|\), and every vertex has degree exactly \(k\geq1\) (\(k\)-regular), then \(G\) has a perfect matching. (This is the regular-graph corollary — reconstruct its proof from Hall's theorem rather than just citing it.)
Solution
Fix \(S\subseteq X\) nonempty. Count edges between \(S\) and \(N(S)\): every vertex of \(S\) has all \(k\) of its edges landing in \(N(S)\) (by definition of \(N(S)\)), so \(e(S,N(S))=k|S|\). On the other hand every vertex of \(N(S)\) has degree \(k\), so it can absorb at most \(k\) edges from \(S\) among its \(k\) total edges: \(e(S,N(S))\leq k|N(S)|\). Combining, \(k|S|\leq k|N(S)|\), and since \(k\geq1\), \(|S|\leq|N(S)|\). This holds for every nonempty \(S\subseteq X\) (and trivially for \(S=\varnothing\)), so Hall's condition holds and \(G\) has a matching \(f\) saturating \(X\). Since \(|X|=|Y|\) and \(f\) is an injection \(X\to Y\) between equal finite sets, \(f\) is a bijection, i.e. a perfect matching.
Give an example of a bipartite graph with \(|X|=|Y|=3\) where every proper nonempty subset \(S\subsetneq X\) strictly satisfies \(|N(S)|\gt|S|\), but \(S=X\) is critical (\(|N(X)|=|X|\)); then verify by direct construction that a perfect matching exists, consistent with Case (ii) of the proof.
Solution
Let \(X=\{x_1,x_2,x_3\}\), \(Y=\{y_1,y_2,y_3\}\) with \(x_1\sim\{y_1,y_2,y_3\}\), \(x_2\sim\{y_1,y_2,y_3\}\), \(x_3\sim\{y_1,y_2,y_3\}\) minus one edge, say \(x_3\sim\{y_1,y_2\}\) only — check: singletons give \(|N|=3\) or \(2\), both \(\gt\) or \(=\) required; pairs: \(N(\{x_1,x_2\})=\{y_1,y_2,y_3\}\), size3\(\gt\)2 ✓ strictly; \(N(\{x_1,x_3\})=\{y_1,y_2,y_3\}\), size3\(\gt\)2 ✓; \(N(\{x_2,x_3\})=\{y_1,y_2,y_3\}\), size3\(\gt\)2 ✓; and \(N(X)=\{y_1,y_2,y_3\}\), size \(3=|X|\), critical. So \(S_0=X\) itself is the only critical set (Case (ii) with \(S_0=X\) is a degenerate instance, but any proper critical subset works too — e.g. modify \(x_3\sim\{y_3\}\) only: then \(S_0=\{x_3\}\) is critical since \(N(\{x_3\})=\{y_3\}\)). Taking this modified graph: \(G_1\) on \(\{x_3\}\cup\{y_3\}\) forces \(x_3\to y_3\); \(G_2\) on \(\{x_1,x_2\}\cup\{y_1,y_2\}\) (both fully connected there) has e.g. \(x_1\to y_1,\ x_2\to y_2\). Glued: \(x_1\to y_1,\ x_2\to y_2,\ x_3\to y_3\), a perfect matching, exactly as Case (ii) predicts.
(Deficiency / converse-style problem.) Let \(X=\{1,2,3,4\}\), \(Y=\{a,b,c\}\), \(1\sim\{a,b\}\),\(2\sim\{a,b\}\),\(3\sim\{a,b,c\}\),\(4\sim\{c\}\). (a) Show Hall's condition fails and identify a violating set with the largest possible deficiency \(|S|-|N(S)|\). (b) State the size of a maximum matching predicted by the deficiency form of the theorem, and exhibit a matching of that size.
Solution
(a) Try \(S=\{1,2,3\}\): \(N(S)=\{a,b,c\}\), size 3, deficiency \(3-3=0\), not violating. Try \(S=\{1,2\}\): \(N(S)=\{a,b\}\), size 2, deficiency 0. The trap subset is \(S=\{1,2,3,4\}=X\): \(N(X)=\{a,b,c\}\), size 3, deficiency \(4-3=1\) — this violates Hall's condition (\(|N(S)|=3\lt4=|S|\)) and is in fact the maximum-deficiency subset, since every smaller subset achieves deficiency \(\leq0\) as checked (also confirm \(S=\{1,3,4\}\): \(N(S)=\{a,b,c\}\), deficiency \(3-3=0\); \(S=\{2,3,4\}\) symmetric; \(S=\{1,2,4\}\): \(N(S)=\{a,b,c\}\), deficiency 0). So the maximum deficiency over all \(S\subseteq X\) is \(1\), attained (only) at \(S=X\). (b) The deficiency form predicts a maximum matching of size \(|X|-\max\text{deficiency}=4-1=3\). Exhibit: \(1\to a,\ 3\to b,\ 4\to c\) (leaving \(2\) unmatched), a valid matching of size 3 using distinct roles from each applicant's allowed set.