Condition
|N(S)| ≥ |S| for every subset S of A
Hall’s condition.
In a bipartite graph with sides and , there is a matching using every vertex of if and only if for every subset , where is the set of neighbours of .
This page is easier if you are comfortable with:
Condition fails exactly when some group is too demanding. If and can only be matched to vertex 1 (, size 1 < 2), no matching covers both. In the first example, , , : every subset satisfies the condition, and indeed , , works. In the second, with and , the best matching has size 2. The theorem is an application of the pigeonhole principle in reverse.
A regular bipartite graph always has a perfect matching, so the complete bipartite graph (see complete bipartite graphs) has perfect matchings (permutations). Hall's theorem can be derived from the max-flow min-cut theorem.
Typical uses are assigning workers to jobs, students to projects or examiners to papers, and the structure of bipartite graphs. For the counting of matchings in weighted problems see assignment-type bounds.
Hall's condition says a matching exists exactly when no group of people has too few possible partners.
Because the neighbour count is smaller, no full matching exists.
These examples are worked by hand, step by step, so you can compare your own working.
With , , , find a matching covering .
With , , find the largest matching.
How many perfect matchings does have?
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
|N(S)| ≥ |S| for every subset S of A
Hall’s condition.
N(a₁) = {b₁, b₂}, N(a₂) = {b₁}, N(a₃) = {b₂, b₃}
All subsets pass.
a₂–b₁, a₁–b₂, a₃–b₃
Perfect matching.
N(a₁) = N(a₂) = {b₁}: |N| = 1 < 2
No matching.
Hall’s theorem: a bipartite graph with parts A and B has a matching saturating A iff |N(S)| ≥ |S| for every subset S ⊆ A. A violating set (|N(S)| < |S|) proves no matching exists.
N(a₁) = {b₁, b₂}, N(a₂) = {b₁}. Check Hall’s condition for S = {a₁, a₂}.
Add N(a₃) = {b₂, b₃}. Check S = {a₁, a₂, a₃}.
Give a perfect matching.
N(a₁) = N(a₂) = {b₁}. Does Hall’s condition hold?
each |N(a)| ≥ 1 ✗
check all subsets ✓
Pairs can fail.
|N(S)| ≤ |S| ✗
|N(S)| ≥ |S| ✓
Neighbours must be at least as many.
requires |A| = |B| ✗
saturating A only ✓
B may be bigger.
|E(S)| ✗
|N(S)| (neighbouring vertices) ✓
Count vertices of B.
Try each one on paper, then open the answer. Use the solver above to see the full working.
1
-1
7
15
5
-1
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
A matching saturating A exists iff |N(S)| ≥ |S| for every S ⊆ A.
Find S with |N(S)| < |S|.
No, only for a perfect matching.
It follows from max-flow min-cut.
max-flow min-cut theorem.
bipartite graphs.
More in Discrete maths and number theory and the formula sheets.