Questions: Graph Matching and Hall's Marriage Theorem

Question 1

A bipartite graph G = (X ∪ Y, E) satisfies |N(S)| ≥ |S| for every subset S ⊆ X. What does Hall's theorem allow you to conclude?

• A. A matching that might cover all of X exists, but it must still be explicitly found
• B. A perfect matching from X to Y is guaranteed to exist
• C. Hall's condition is necessary but not sufficient, so additional conditions are required
• D. A perfect matching exists only if |X| = |Y|

Answer: (B)

Hall's theorem states the condition is both necessary AND sufficient. If Hall's condition holds for every subset S ⊆ X, a perfect matching (covering all of X) is guaranteed to exist — the condition alone certifies this without needing to construct the matching. Sufficiency is the deep result: checking a local neighborhood condition guarantees a global combinatorial structure.

Question 2

Four students must each be assigned to a distinct club they qualify for. Three of the students are only qualified for the same 2 clubs. What does Hall's theorem say about whether a valid assignment exists?

• A. A valid assignment might still exist — it depends on the fourth student's qualifications
• B. No complete assignment can exist, because 3 students share only 2 qualifying clubs, violating Hall's condition
• C. Hall's theorem cannot be applied because the bipartite graph is not regular
• D. A valid assignment exists as long as the fourth student qualifies for at least 2 clubs

Answer: (B)

Hall's condition requires that for every subset S ⊆ X, |N(S)| ≥ |S|. The subset S consisting of the 3 students with only 2 qualifying clubs has |N(S)| = 2 < 3 = |S|. Hall's condition fails for this subset, so no perfect matching exists — regardless of the fourth student's qualifications. The failure of one subset is enough to certify impossibility.

Question 3

If Hall's condition fails for even one subset S ⊆ X, then no perfect matching from X to Y can exist.

• T. True
• F. False

Answer: True

Hall's theorem is an if-and-only-if result. A perfect matching exists precisely when Hall's condition holds for ALL subsets. A single violating subset S with |N(S)| < |S| means there are more vertices in S than distinct neighbors to match them to — at least |S| − |N(S)| vertices in S must go unmatched. The necessity direction of Hall's theorem confirms this directly.

Question 4

In a bipartite graph where |X| = |Y|, a perfect matching is very likely to exist.

• T. True
• F. False

Answer: False

Equal set sizes are not sufficient for a perfect matching. A bipartite graph with |X| = |Y| can still violate Hall's condition: for instance, if every vertex in X connects only to the same single vertex in Y. Hall's theorem requires that |N(S)| ≥ |S| for every subset S ⊆ X — a condition about the structure of neighborhoods, not just overall set sizes.

Question 5

What is the key difference between the 'necessary' and 'sufficient' directions of Hall's theorem, and which direction is the more surprising mathematical result?

Model answer: The necessary direction says: if a perfect matching exists, Hall's condition must hold — this is obvious, because matching |S| vertices requires |S| distinct neighbors. The sufficient direction says: if Hall's condition holds for every S ⊆ X, a perfect matching is guaranteed to exist — this is the deep result, proven by induction. It asserts that when no subset has too few neighbors, no obstruction to matching exists at all. Sufficiency is more surprising because it converts a local neighborhood condition into a guarantee of a global combinatorial structure.

The sufficient direction is non-trivial because there is no obvious reason why satisfying Hall's condition for all subsets prevents some other, subtler obstruction. The proof shows, by considering the 'tightest' subsets, that no other obstruction is possible — a beautiful example of a necessary condition being exactly tight.