A bipartite graph has a matching that saturates one of its two sides if and only if every subset of that side has at least as many neighbors, collectively, as its own size (Hall's condition). Proved by Philip Hall, it is a foundational existence result in combinatorics with wide application to assignment and scheduling problems.
Facts
StatementFor a finite family of finite sets, a system of distinct representatives, one representative chosen from each set with no repetition, exists exactly when every subfamily's own sets have a union at least as large as the number of sets in that subfamily. In graph terms, a finite bipartite graph has a matching that covers one side exactly when every subset of that side has a neighborhood at least as large as the subset itself. 1 Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Sources
1. Hall's Marriage Theorem (Wikipedia)
Wikimedia FoundationCombinatorial formulation section
Hall's condition is that for any subset of sets from the collection, the total unique elements they contain is at least as large as the number of sets in the subset.
Lead section
In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.