Hall's marriage theorem

Hall's marriage theorem states that a finite family of sets has a system of distinct representatives exactly when every subfamily's union contains at least as many elements as the subfamily.

System of distinct representatives: A selection of one element from each set in a family, with no selected element repeated. The theorem gives the exact condition for such a selection to exist.
Set family: A collection of sets considered together as a mathematical object. The theorem applies to finite collections of sets, not only to pairs or graphs.
Bipartite matching problem: The problem of finding a largest set of pairwise vertex-disjoint edges in a bipartite graph. Hall's theorem characterizes when a matching can cover one entire side.
Kőnig's theorem: A theorem stating that a bipartite graph's maximum matching size equals its minimum vertex-cover size. It relates matching size to a different optimization problem rather than testing a full-side matching.
Bipartite graph: A graph whose vertices divide into two parts, with every edge joining vertices in different parts. Sets and their possible representatives become the two vertex classes, joined by membership edges.
Union (set theory): The set containing every element that belongs to at least one set in a given collection. Hall's condition compares each subfamily's union with the number of sets in that subfamily.
Marriage problem: An assignment problem asking whether each member of one group can be paired with a distinct acceptable member of another. This motivating assignment gives the theorem its name and its simplest interpretation.
Marriage theorem for infinite sets: Extensions of Hall's theorem that address representative selections from infinite families under additional hypotheses. The finite theorem's condition alone does not capture every issue in infinite settings.
Matching: A set of graph edges no two of which share a vertex. A matching covering every set-vertex encodes distinct representatives.
Injective function: A function that maps distinct inputs to distinct outputs. Choosing distinct representatives is an injective assignment from sets to their elements.

Linked from 13 pages