Hall's Theorem
For a subset , let be the set of all right vertices adjacent to at least one vertex in . Each right vertex is counted once, even if it has several neighbors in .
Hall's theorem states that a matching saturating exists if and only if
Here, saturating means matching every left vertex. The condition says that every subset of left vertices must have at least as many distinct neighbors.
Suppose every left vertex is matched. The vertices in any subset have distinct matched partners, all belonging to . Therefore,
Take a maximum matching. Suppose it leaves left vertices unmatched.
Start a search from all these vertices. Follow unmatched edges from to and matched edges from to , as in the vertex-cover construction. Let and be the visited vertices.
Every neighbor of belongs to :
Conversely, every vertex in was reached from a neighbor in . Hence
Every vertex in is matched; reaching an unmatched right vertex would give an augmenting path. These right vertices are paired with exactly the matched vertices in .
The remaining vertices in are the unmatched starting vertices. Thus
This contradicts Hall's condition for . Therefore, if the condition holds, a maximum matching saturates .
Compute a maximum matching. If its size is , every left vertex can be matched. Otherwise, run the alternating search above. It produces
This subset explains why a complete assignment is impossible: its vertices have too few distinct possible partners.
Given sets , a system of distinct representatives chooses
with all chosen values different.
Create a left vertex for each set and a right vertex for each distinct value. Connect set to every value it contains. The required choices are exactly a matching saturating the left side.
Hall's theorem gives the condition
Every group of sets must contain at least as many distinct values as there are sets in the group. Count the union of their choices; adding the individual set sizes would count shared values more than once.