Hall's Marriage Theorem

Hall's Theorem gives a necessary and sufficient condition for a bipartite graph to have a matching that covers one side of the partition. It is often framed as a "marriage" problem between a set of men and women.

The Condition

Consider a bipartite graph $G = (X \cup Y, E)$ . For any subset $S \subseteq X$ , let $N (S)$ be the set of neighbors of vertices in $S$ (the set of vertices in $Y$ connected to at least one vertex in $S$ ).

Theorem (Hall's Marriage Theorem)

The graph

G

contains a matching that covers every vertex in

X

if and only if for every subset

S \subseteq X

∣ N (S) ∣ \geq ∣ S ∣

Interpretation

"For every group of men, the total number of women they collectively like must be at least as large as the group of men." If a group of 3 men collectively only like 2 women, a matching is clearly impossible. Hall's Theorem states this is the only obstruction.

Systems of Distinct Representatives (SDR)

Hall's Theorem applies to sets. Given sets

A_{1}, A_{2}, \dots, A_{n}

, an SDR is a choice of distinct elements

x_{1}, \dots, x_{n}

such that

x_{i} \in A_{i}

Condition: For any $k$ sets, their union must contain at least $k$ elements.

Practice Problems

Exercise (Problem 1)

A deck of cards is dealt into 13 piles of 4 cards each. Prove that it is possible to select one card from each pile such that the 13 selected cards contain exactly one card of each rank (Ace through King).

Exercise (Problem 2)

Prove that a

k

-regular bipartite graph (

k \geq 1

) always has a perfect matching.

Exercise (Problem 3)

Check if a matching covering

X

exists for

X = {1, 2, 3}

Y = {A, B}

, with edges

(1, A), (2, A), (2, B), (3, B)