Hall's Marriage Theorem: Intuition, Proofs, and Competitive Programming Applications
In bipartite graph theory and combinatorial optimization, one of the most fundamental questions is: When can every vertex on the left side of a bipartite graph be matched to a distinct vertex on the right side? While maximum flow and augmenting path algorithms (such as Hopcroft–Karp or Kuhn’s algorithm) allow us to compute a maximum matching for a fixed graph, Hall’s Marriage Theorem (proved by Philip Hall in 1935) gives a clean necessary and sufficient structural condition for a complete matching to exist. In competitive programming, Hall’s theorem often allows us to bypass building an explicit flow network altogether—transforming matching feasibility problems into algebraic inequalities, prefix/interval checks, or Sum Over Subsets Dynamic Programming (SOS DP). ...