Questions: Hall's Marriage Theorem

Question 1

You check Hall's condition for every individual vertex v in A and confirm that each has at least one neighbor in B. Can you conclude a perfect matching exists?

• A. Yes — if every vertex has at least one neighbor, a matching can always be constructed
• B. No — Hall's condition must hold for all subsets of A, not just individual vertices. A group of vertices may collectively have too few neighbors even if each has one individually
• C. Yes — individual vertex checks are sufficient when |A| = |B|
• D. No — you must also verify that each vertex in B has at least one neighbor

Answer: (B)

This is the central trap. Suppose A has four vertices {a₁, a₂, a₃, a₄} and each is connected to at least one vertex in B — but a₁, a₂, a₃, and a₄ are ALL connected to only the same three vertices {b₁, b₂, b₃}. Every vertex individually passes the check (|N({aᵢ})| ≥ 1), but the subset S = {a₁, a₂, a₃, a₄} has |N(S)| = 3 < 4 = |S| — Hall's condition fails. No perfect matching can accommodate all four. You must verify Hall's condition for all 2^|A| subsets.

Question 2

Suppose Hall's condition fails for a specific subset S ⊆ A with |N(S)| < |S|. Why is finding this 'Hall set' S useful beyond just proving no perfect matching exists?

• A. It proves the graph is not bipartite
• B. It precisely identifies the bottleneck — the group of left vertices with insufficient collective options — pinpointing where any attempted matching must break down
• C. It allows you to compute the maximum independent set instead
• D. It proves that the graph has no matching of any size

Answer: (B)

A Hall set is diagnostically valuable: it tells you exactly which group of vertices is causing the impossibility and why — they collectively need more matches than exist in their collective neighborhood. This localization makes Hall's theorem as useful for proving non-existence as for guaranteeing existence. In applications like assignment problems, identifying the Hall set tells you precisely which constraints conflict and what must change (add resources, relax requirements) to make a perfect matching possible. Option D is wrong — the graph may still have large partial matchings even if a perfect one doesn't exist.

Question 3

Hall's condition is necessary for a perfect matching to exist, but not sufficient — there exist bipartite graphs where Hall's condition holds for most subset yet no perfect matching exists.

• T. True
• F. False

Answer: False

Hall's Marriage Theorem proves the condition is both necessary AND sufficient. The 'if and only if' is the theorem's power: Hall's condition holding for all subsets S ⊆ A is a complete characterization of when a perfect matching exists. Necessity is immediate (a matching injects S into N(S)). Sufficiency — that the condition guarantees a matching — is the deeper and non-obvious direction, proved by induction. Many theorems give only necessary conditions; Hall's theorem gives a complete criterion.

Question 4

If Hall's condition |N(S)| ≥ |S| holds for every subset S of A, then a perfect matching from A to B is guaranteed to exist.

• T. True
• F. False

Answer: True

This is precisely the statement of Hall's Marriage Theorem (the sufficiency direction). The condition being necessary is easy to see — a perfect matching injects each subset S into distinct vertices of N(S). The remarkable fact is that the condition is also sufficient: whenever no bottleneck exists (every group has enough options), a perfect matching can always be constructed. The proof by strong induction shows that you can always find an augmenting extension of any partial matching when Hall's condition holds throughout.

Question 5

Explain why checking Hall's condition only for individual vertices is insufficient, and give a concrete example where individual checks pass but a perfect matching fails to exist.

Model answer: Individual vertex checks only verify that each vertex has at least one option — they say nothing about whether groups of vertices collectively have enough distinct options. Example: let A = {a₁, a₂, a₃} and B = {b₁, b₂, b₃}, with a₁, a₂, and a₃ all connected only to b₁ and b₂. Each vertex individually has neighbors (|N({aᵢ})| = 2 ≥ 1), so individual checks pass. But N({a₁, a₂, a₃}) = {b₁, b₂}, so |N(S)| = 2 < 3 = |S|. The three vertices in A must all share only two options in B — no perfect matching can assign them all distinct partners.

The Hall condition must hold for all 2^|A| subsets because the bottleneck constraint — too many left vertices competing for too few right vertices — is inherently a group property. A group of k vertices can collectively exhaust fewer than k options even if each one has options individually. This is the 'marriage problem' intuition: each suitor may be compatible with someone, but if many suitors are only compatible with the same small pool, the group as a whole faces a bottleneck.