# Hall’s marriage theorem

Let $S=\{S_{1},S_{2},\dots S_{n}\}$ be a finite collection  of finite sets  . There exists a system of distinct representatives of $S$ if and only if the following condition holds for any $T\subseteq S$:

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

As a corollary, if this condition fails to hold anywhere, then no SDR exists.

This is known as Hall’s marriage theorem  . The name arises from a particular application of this theorem. Suppose we have a finite set of single men/women, and, for each man/woman, a finite collection of women/men to whom this person is attracted. An SDR for this collection would be a way each man/woman could be (theoretically) married happily. Hence, Hall’s marriage theorem can be used to determine if this is possible.

An application of this theorem to graph theory  gives that if $G(V_{1},V_{2},E)$ is a bipartite graph  , then $G$ has a complete matching that saturates every vertex of $V_{1}$ if and only if $|S|\leq|N(S)|$ for every subset $S\subset V_{1}$.

Title Hall’s marriage theorem HallsMarriageTheorem 2013-03-22 12:35:14 2013-03-22 12:35:14 mathcam (2727) mathcam (2727) 6 mathcam (2727) Theorem msc 05D15 marriage theorem Saturate