# Hall’s marriage theorem, proof of

We prove Hall’s marriage theorem by induction on $\left|S\right|$, the size of $S$.

The theorem is trivially true for $|S|=0$.

Assuming the theorem true for all $\left|S\right|, we prove it for $\left|S\right|=n$.

First suppose that we have the stronger condition

 $\left|\cup T\right|\geq\left|T\right|+1$

for all $\emptyset\neq T\subset S$. Pick any $x\in S_{n}$ as the representative of $S_{n}$; we must choose an SDR from

 $S^{\prime}=\left\{S_{1}\setminus\{x\},\ldots,S_{n-1}\setminus\{x\}\right\}.$

But if

 $\{S_{j_{1}}\setminus\{x\},...,S_{j_{k}}\setminus\{x\}\}=T^{\prime}\subseteq S^% {\prime}$

then, by our assumption,

 $\left|\cup T^{\prime}\right|\geq\left|\cup_{i=1}^{k}S_{j_{i}}\right|-1\geq k.$

By the already-proven case of the theorem for $S^{\prime}$ we see that we can indeed pick an SDR for $S^{\prime}$.

Otherwise, for some $\emptyset\neq T\subset S$ we have the “exact” size

 $\left|\cup T\right|=\left|T\right|.$

Inside $T$ itself, for any $T^{\prime}\subseteq T\subset S$ we have

 $\left|\cup T^{\prime}\right|\geq\left|T^{\prime}\right|,$

so by an already-proven case of the theorem we can pick an SDR for $T$.

It remains to pick an SDR for $S\setminus T$ which avoids all elements of $\cup T$ (these elements are in the SDR for $T$). To use the already-proven case of the theorem (again) and do this, we must show that for any $T^{\prime}\subseteq S\setminus T$, even after discarding elements of $\cup T$ there remain enough elements in $\cup T^{\prime}$: we must prove

 $\left|\cup T^{\prime}\setminus\cup T\right|\geq\left|T^{\prime}\right|.$

But

 $\displaystyle\left|\cup T^{\prime}\setminus\cup T\right|$ $\displaystyle=\left|\bigcup(T\cup T^{\prime})\right|-\left|\cup T\right|\geq$ (1) $\displaystyle\geq\left|T\cup T^{\prime}\right|-\left|T\right|=$ (2) $\displaystyle=\left|T\right|+\left|T^{\prime}\right|-\left|T\right|=\left|T^{% \prime}\right|,$ (3)

using the disjointness of $T$ and $T^{\prime}$. So by an already-proven case of the theorem, $S\setminus T$ does indeed have an SDR which avoids all elements of $\cup T$.

This the proof.

Title Hall’s marriage theorem, proof of HallsMarriageTheoremProofOf 2013-03-22 12:45:12 2013-03-22 12:45:12 mps (409) mps (409) 10 mps (409) Proof msc 05D15