# Hall’s marriage theorem

Let $S=\{{S}_{1},{S}_{2},\mathrm{\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|\ge |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|\le |N(S)|$ for every subset $S\subset {V}_{1}$.

Title | Hall’s marriage theorem |
---|---|

Canonical name | HallsMarriageTheorem |

Date of creation | 2013-03-22 12:35:14 |

Last modified on | 2013-03-22 12:35:14 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 6 |

Author | mathcam (2727) |

Entry type | Theorem |

Classification | msc 05D15 |

Synonym | marriage theorem |

Related topic | Saturate |