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).
Marriage Theorem
See also
MatchingExplore with Wolfram|Alpha
References
Chartrand, G. Introductory Graph Theory. New York: Dover, 1985.Hall, P. "On Representatives of Subsets." J. London Math. Soc. 10, 26-30, 1935.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Referenced on Wolfram|Alpha
Marriage TheoremCite this as:
Weisstein, Eric W. "Marriage Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MarriageTheorem.html