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)

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)

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\},

|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
Some subset satisfies (	N(A)
$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

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.

Prove that every perfect matching in a bipartite graph satisfies Hall’s condition.
Show that the complete bipartite graph $K_{n,n}$ has a perfect matching.
Let

A_1=\{1,2\}, \quad A_2=\{2,3\}, \quad A_3=\{1,3\}.

Find a system of distinct representatives.

Give an example of a bipartite graph where Hall’s condition fails.
Prove that every $1$ -regular bipartite graph has a perfect matching.
Let $G$ be bipartite. Show that if some subset $A \subseteq X$ satisfies

|N(A)|<|A|,

then no matching can saturate $X$ .

Prove Hall’s theorem for the case $|X|=2$ .
Show that every cycle $C_{2n}$ has a perfect matching by using Hall’s theorem.
Explain why Hall’s theorem implies that every regular bipartite graph has a perfect matching.

Chapter 58. Hall's Marriage Theorem

Chapter 58. Hall’s Marriage Theorem

58.1 Bipartite Graphs

58.2 Neighborhoods

58.3 Hall’s Condition

58.4 Hall’s Marriage Theorem

58.5 Necessity of Hall’s Condition

58.6 Proof of Sufficiency

Case 1

Case 2

58.7 Marriage Interpretation

58.8 Perfect Matchings in Bipartite Graphs

58.9 Systems of Distinct Representatives

58.10 Examples

Example 1

Example 2

58.11 Regular Bipartite Graphs

Proof

58.12 Hall’s Theorem and Flows

58.13 Hall’s Theorem and Latin Squares

58.14 Deficiency

58.15 Infinite Hall Theorem

58.16 Common Consequences

58.17 Historical Notes

58.18 Exercises