Hall’s marriage theorem


Let S={S1,S2,Sn} be a finite collectionMathworldPlanetmath of finite setsMathworldPlanetmath. There exists a system of distinct representatives of S if and only if the following condition holds for any TS:

|T||T|

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

This is known as Hall’s marriage theoremMathworldPlanetmath. 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 theoryMathworldPlanetmath gives that if G(V1,V2,E) is a bipartite graphMathworldPlanetmath, then G has a complete matching that saturates every vertex of V1 if and only if |S||N(S)| for every subset SV1.

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