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 , we prove it for $\left|S\right|=n$.

First suppose that we have the stronger condition

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

for all $\mathrm{\varnothing }\ne T\subset S$. Pick any $x\in S_n$ as the representative of $S_n$; we must choose an SDR from

$$S^{\prime }=\{S_1\setminus \{x\},\mathrm{\dots },S_{n-1}\setminus \{x\}\}.$$

But if

$$\{S_{j_1}\setminus \{x\},\mathrm{\dots },S_{j_k}\setminus \{x\}\}=T^{\prime }\subseteq S^{\prime }$$

then, by our assumption,

$$\left|\cup T^{\prime }\right|\ge \left|{\cup }_{i=1}^k{S}_{j_i}\right|-1\ge 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 $\mathrm{\varnothing }\ne 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|\ge \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

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

But

$|\cup T^{\prime }\setminus \cup T|$ $=\left|{\displaystyle \bigcup (T\cup T^{\prime })}\right|-\left|\cup T\right|\ge$ (1)

$\ge \left|T\cup T^{\prime }\right|-\left|T\right|=$ (2)

$=\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
Canonical name	HallsMarriageTheoremProofOf
Date of creation	2013-03-22 12:45:12
Last modified on	2013-03-22 12:45:12
Owner	mps (409)
Last modified by	mps (409)
Numerical id	10
Author	mps (409)
Entry type	Proof
Classification	msc 05D15