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. Combinatorial formulation Statement 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