Hall's Marriage Theorem Explained with Worked Examples

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 .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Hall's marriage theorem means

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.

What is it used for?

Hall's condition says a matching exists exactly when no group of people has too few possible partners.

How to use hall's marriage theorem

  1. Identify the two sides and .
  2. For each subset of , list the neighbours .
  3. Check .
  4. If one subset fails, there is no matching covering ; otherwise one exists.

Graph

A failing subset: S = {a, b} has 2 members but only 1 neighbour|S| = 2|N(S)| = 100.511.522.5300.511.522.5A failing subset: S = {a, b} has 2 members but only 1 neighbourquantityyGraph with x from 0 to 3 and y from 0 to 2.6. Shows bars (2); point |S| = 2 at (1, 2); point |N(S)| = 1 at (2, 1).

Because the neighbour count is smaller, no full matching exists.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: Hall holds

With , , , find a matching covering .

Worked example
Answer
3 edges (complete)3\text{ edges (complete)}
  1. b
  2. a
  3. c

Example 2: Hall fails

With , , find the largest matching.

Worked example
Answer
22
  1. S = {a,b}
  2. Largest matching

Example 3: perfect matchings of K₃,₃

How many perfect matchings does have?

Worked example
Answer
66
  1. Choices

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

Condition

|N(S)| ≥ |S| for every subset S of A

Hall’s condition.

Example

N(a₁) = {b₁, b₂}, N(a₂) = {b₁}, N(a₃) = {b₂, b₃}

All subsets pass.

Matching

a₂–b₁, a₁–b₂, a₃–b₃

Perfect matching.

Failure

N(a₁) = N(a₂) = {b₁}: |N| = 1 < 2

No matching.

Word problems

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.

Check S = {a₁, a₂}

N(a₁) = {b₁, b₂}, N(a₂) = {b₁}. Check Hall’s condition for S = {a₁, a₂}.

  1. N(S){b₁, b₂}, size 2
  2. |S|2
  3. Check: 2 ≥ 2 ✓Holds.

All of A

Add N(a₃) = {b₂, b₃}. Check S = {a₁, a₂, a₃}.

  1. N(S){b₁, b₂, b₃}, size 3
  2. Check: 3 ≥ 3 ✓Holds.

Find a matching Higher

Give a perfect matching.

  1. a₂–b₁
  2. a₁–b₂
  3. a₃–b₃
  4. Check: three disjoint edges ✓As listed.

A violation Higher

N(a₁) = N(a₂) = {b₁}. Does Hall’s condition hold?

  1. |N({a₁, a₂})|1
  2. |S|2
  3. Check: 1 < 2, no matching ✓No.

Common mistakes

Checking only single vertices

each |N(a)| ≥ 1 ✗

check all subsets ✓

Pairs can fail.

Mixing up the parts

|N(S)| ≤ |S| ✗

|N(S)| ≥ |S| ✓

Neighbours must be at least as many.

Needing a perfect matching

requires |A| = |B| ✗

saturating A only ✓

B may be bigger.

Counting edges not vertices

|E(S)| ✗

|N(S)| (neighbouring vertices) ✓

Count vertices of B.

Exam tips

  1. |N(S)| ≥ |S| for all S.
  2. Test every subset.
  3. Find a violation to disprove.
  4. Saturates A.
  5. Link to max flow.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. |N(S)| − |S| for |N| = 3, |S| = 2 Foundation

1

2. |N(S)| − |S| for |N| = 2, |S| = 3 Foundation

-1

3. Subsets of {a₁, a₂, a₃} (non-empty) Foundation

7

4. Subsets to check for |A| = 4 Higher

15

5. Edges in a perfect matching of 5 pairs Higher

5

6. |N(S)| − |S| for |N| = 1, |S| = 2 Higher

-1

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Hall’s theorem
Condition for a matching saturating A.
Neighbourhood N(S)
Vertices adjacent to S.
Matching
Disjoint edges.
Perfect matching
Covers all vertices.
Saturate
Cover every vertex of A.
Bipartite graph
Two-part graph.

Frequently asked questions

What is Hall’s marriage theorem?

A matching saturating A exists iff |N(S)| ≥ |S| for every S ⊆ A.

How do I disprove a matching?

Find S with |N(S)| < |S|.

Is |A| = |B| required?

No, only for a perfect matching.

How does it link to flows?

It follows from max-flow min-cut.

Which page covers max-flow min-cut?

max-flow min-cut theorem.

Which page covers bipartite graphs?

bipartite graphs.

More in Discrete maths and number theory and the formula sheets.