In mathematics, the marriage theorem, usually credited to mathematician Philip Hall, is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of subsets.

Let S = {S_i} be a (possibly infinite) set of finite subsets of some larger collection. A set of distinct representatives (sometimes abbreviated as an SDR) is a set X = {x_i} with the property that for all i, x_i is in S_i, and x_i ≠ x_j if i ≠ j.

The marriage condition for S is that, for any subset T = {T_i} of S,

The marriage theorem then states that there exists a set of distinct representatives X = {x_i} if and only if S meets the marriage condition.

The standard example (somewhat dated at this point) of an application of the marriage theorem is to imagine two groups of n men and women. Each woman would happily marry some subset of the men; and any man would be happy to marry a woman who wants to marry him.

If we let M_i be the set of men that the ith woman would be happy to marry, then each woman can happily marry a man if and only if the collection of sets {M_i} meets the marriage condition.

The theorem has many other interesting "non-marital" applications. For example, take a standard deck of cards, and deal them out into 13 piles of 4 cards each. Then, using the marriage theorem, we can show that it is possible to select exactly 1 card from each pile, such that the 13 selected cards contain exactly one card of each rank (ace, 2, 3, ..., queen, king).

More abstractly, let G be a group, and H be a finite subgroup of G. Then the marriage theorem can be used to show that there is a set X such that X is an SDR for both the set of left cosets and right cosets of H in G.

Graph theory

The marriage theorem has applications in the area of graph theory. Formulated in graph theoretic terms the problem can be stated as:

Given a bipartite graph G:=(S + T, E) with two equally sized partitions S and T does there exist a perfect matching ?

The marriage theorem provides the answer:

A perfect matching exists if and only if for every subset X of S

with N_G(X) the neighborhood of X. In other words every subset X has enough adjacent vertices in T.

A generalization to arbitrary graphs is provided by Tutte theorem.

External links

• Marriage Theorem
• Marriage Theorem and Algorithm