Hall's marriage theorem

In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), 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.