Hall's marriage theorem

Imagine a town where each person on one side has a list of people on the other side they would be willing to marry, and we want to marry off everyone on the first side, each to a distinct partner from their own list. When is that possible? Hall's marriage theorem gives the exact, surprisingly simple condition: it is possible if and only if no group of people is collectively too picky.

Formally, take a bipartite graph with left side L and right side R; we seek a matching that saturates L (matches every left vertex). For any subset A of L, let N(A) be the set of right vertices adjacent to at least one vertex in A — the combined option pool of A. Hall's condition is: for every subset A of L, |N(A)| >= |A|. The theorem says a left-saturating matching exists exactly when this holds. The 'only if' direction is obvious — if some A has fewer neighbors than members, those members cannot all be matched to distinct partners. The 'if' direction is the deep part and follows cleanly from max-flow min-cut (or from Konig's theorem): if no perfect matching existed, the maximum matching would miss some left vertex, and tracing the min cut produces a violating set A with |N(A)| < |A|, contradicting the condition.

Hall's theorem is the cornerstone of matching theory and a beautiful example of a min-max / feasibility certificate: either a full matching exists, or there is a single 'deficient set' A that proves it cannot, with nothing in between. It underlies results from combinatorics (systems of distinct representatives, Latin squares) to scheduling. Two honest cautions. First, the condition must hold for every subset A, of which there are exponentially many — so Hall's theorem is a characterization, not a fast test; you actually find or refute the matching with a flow algorithm, then Hall explains why. Second, |N(A)| >= |A| guarantees you can match all of L, not all of R; saturating both sides (a perfect matching) needs |L| = |R| as well.