Discrete Mathematical Structures by Pearson

Topics in Graph Theory 10-65

In terms of matrimonial terminology, we can observe that, for the solution of the marriage

problem, every set of k boys must have at least k girlfriends for all integers k where 1 ≤ k ≤ m.

This condition is known as marriage condition. It is a necessary condition, which if not

satisfied boys would not be able to marry the girls in that set. This marriage condition also turns

out to be sufficient.

THEOREM 10.17 (Hall’s Marriage Theorem)

A necessary and sufficient condition for the solution of marriage problem is that each set of k

girls collectively knows at least k boys for 1 ≤ k ≤ m.

This result can be presented in ...