Hall’s marriage theorem
Let be a finite collection of finite sets. There exists a system of distinct representatives of if and only if the following condition holds for any :
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 is a bipartite graph, then has a complete matching that saturates every vertex of if and only if for every subset .
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 |