The marriage theorem states that if a group of men and women may date only if they have previously been introduced, then a complete set of dates is possible iff
every subset of men has collectively been introduced to at least as many women, and
vice versa (Hall 1935; Chartrand 1985, p. 121; Skiena 1990, p. 240).
Despite the similar terminology, this matching theorem is distinct from the sequential optimal-stopping secretary problem, also known
as the marriage problem, and the preference-based stable
marriage problem.
