# 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 |