= Hall's marriage theorem
{c}
{wiki}
= Hall marriage theorem
{c}
{synonym}
For a finite <bipartite graph> $G=(L\cup R,E)$ with disjoint left and right <vertex sets>, <Hall's marriage theorem> characterizes when distinct allowed partners can be chosen for every left <vertex>. A <matching in a graph> with <matching saturation> of $L$ exists \b[if and only if] every <subset> $S\subseteq L$ satisfies
$$
|N_G(S)|\geq |S|,\qquad N_G(S)=\{r\in R:\text{some }s\in S\text{ has }sr\in E\}.
$$
The <graph neighbourhood> counts distinct right <vertices>, rather than <edges> or repeated choices. This is the <Hall condition>. Its failure supplies a concrete <Hall obstruction>. Necessity follows because the chosen partners of $S$ are distinct members of $N_G(S)$; sufficiency is the surprising assertion that these collective counts rule out every obstacle.<Graph Theory by Reinhard Diestel>[Matching, Covering and Packing, 4th electronic edition 2010, corrected reprint 2012, §2.1, printed pp. 3–4, Theorem 2.1.2: matching of the specified part]{ref}
The right side may be larger: <matching saturation> of $L$ leaves $|R|-|L|$ right <vertices> unmatched. Only when $|L|=|R|$ does a <matching in a graph> saturating $L$ automatically become a <perfect matching>. For a specified <subset> $X\subseteq L$, apply the same criterion only to $S\subseteq X$, using the <induced subgraph> on $X\cup R$. The remaining left <vertices> need not be matched. The empty <set> gives $0\geq0$; if $X$ is empty, the empty <matching in a graph> suffices.
Consider a <scheduling> model with three unit-duration jobs $a,b,c$ and four available slots $1,2,3,4$ on one machine. Each job needs exactly one slot, each slot accepts at most one job, and the allowed slots are
$$
N(a)=\{1,2\},\qquad N(b)=\{1\},\qquad N(c)=\{2,3,4\}.
$$
The <bipartite graph> below admits $M=\{a2,b1,c3\}$, a <matching in a graph> saturating all jobs while leaving slot $4$ unused. It is not a <perfect matching> of the seven-<vertex> <graph>. A greedy choice $a1$ initially blocks $b$, but the <augmenting path in a matching> $b,1,a,2$ replaces $a1$ by $b1,a2$; subsequent assignment of $c3$ succeeds. A bad partial choice is not an impossibility certificate.
\Image[/hall-matching-three-jobs-four-slots.png]
{title=A <matching in a graph> saturates all three jobs and leaves one of four slots unused}
{description=Thick blue <edges> are $a2,b1,c3$; thin grey <edges> are other allowed assignments. Crossings are not <vertices>.}
There are eight <subsets> of $L=\{a,b,c\}$. Listing each <graph neighbourhood> makes the all-<subset> requirement explicit:
|| $S$
|| $N(S)$
|| $|S|$
|| $|N(S)|$
| $\varnothing$
| $\varnothing$
| 0
| 0
| $\{a\}$
| $\{1,2\}$
| 1
| 2
| $\{b\}$
| $\{1\}$
| 1
| 1
| $\{c\}$
| $\{2,3,4\}$
| 1
| 3
| $\{a,b\}$
| $\{1,2\}$
| 2
| 2
| $\{a,c\}$
| $\{1,2,3,4\}$
| 2
| 4
| $\{b,c\}$
| $\{1,2,3,4\}$
| 2
| 4
| $\{a,b,c\}$
| $\{1,2,3,4\}$
| 3
| 4
There are exactly two <matchings in a graph> saturating $L$: $\{a2,b1,c3\}$ and $\{a2,b1,c4\}$. Job $b$ forces slot $1$, then job $a$ forces slot $2$, leaving two choices for $c$.
Back to article page
