Hall's Marriage Theorem

Graph Theory · Axiom Academy

LESSON Hall's Marriage Theorem A fundamental result in matching theory that characterizes when perfect matchings exist in bipartite graphs Imagine a community with men and women. Each man knows some women. Can we arrange marriages so that every man marries a woman he knows, with each woman marrying at most one man? We model this as a bipartite graph where one set represents men, the other represents women, and edges represent acquaintances. Hall's theorem states that a perfect matching exists if and only if the Hall's condition holds: For every subset S of X, the neighborhood N(S) must be at least as large as S itself. In other words: "No group of men can collectively know fewer women than there are men in the group." 3. Example: Hall's Condition Satisfied Let's verify Hall's condition for a small bipartite graph. We'll check several subsets to see that |N(S)| ≥ |S| holds. 4. Example: Hall's Condition Violated Now consider a graph where Hall's condition fails. There exists a subset S where |N(S)| < |S|, making a perfect matching impossible. 5. Applications and Proof Sketch Job Assignments: Can we assign n workers to n jobs if each worker is qualified for certain jobs? Systems of Distinct Representatives (SDRs): Given sets S₁, S₂, ..., Sₙ, can we pick distinct elements x₁ ∈ S₁, x₂ ∈ S₂, ..., xₙ ∈ Sₙ? Schedule Matching: Assigning time slots to events with availability constraints.

This is the written version of the interactive lesson above. See the full Graph Theory course.