Hall's marriage theorem

In mathematics, Hall's marriage theorem, proved by , is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist: The combinatorial formulation answers whether a finite collection of sets has a transversal—that is, whether an element can be chosen from each set without repetition. Hall's condition is that for any group of sets from the collection, the total unique elements they contain is at least as large as the number of sets in the group. The graph theoretic formulation answers whether a finite bipartite graph has a perfect matching—that is, a way to match each vertex from one group uniquely to an adjacent vertex from the other group. Hall's condition is that any subset of vertices from one group has a neighbourhood of equal or greater size. Let be a finite family of sets (note that although is not itself allowed to be infinite, the sets in it may be so, and may contain the same set multiple times). Let be the union of all the sets in , the set of elements that belong to at least one of its sets. A transversal for is a subset of that can be obtained by choosing a distinct element from each set in . This concept can be formalized by defining a transversal to be the of an injective function such that for each . An alternative term for transversal is system of distinct representatives. The collection satisfies the marriage condition when each subfamily of contains at least as many distinct members as its number of sets. That is, for all , If a transversal exists then the marriage condition must be true: the function used to define the transversal maps to a subset of its union, of size equal to , so the whole union must be at least as large. Hall's theorem states that the converse is also true: Example 1 Consider the family with and The transversal could be generated by the function that maps to , to , and to , or alternatively by the function that maps to , to , and to . There are other transversals, such as and .