Marriage Theorem

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).

See also


Explore with Wolfram|Alpha


More things to try:


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 Theorem

Cite this as:

Weisstein, Eric W. "Marriage Theorem." From MathWorld--A Wolfram Web Resource.

Subject classifications