Hall's Marriage Theorem/Explanation
Jump to navigation
Jump to search
Hall's Marriage Theorem: Explanation
This Hall's Marriage Theorem is so called for the following reason:
Let $I$ be a set of women.
Suppose that each woman $k$ is romantically interested in a finite set $S_k$ of men.
Suppose also that:
- each woman would like to marry exactly one of these men
and:
- each man in $\ds \bigcup_{k \mathop \in I} S_k$ would like to marry at most one woman in $I$.
Then this theorem gives a condition under which it is possible to match every woman to a man.