Five job applicants each have exactly two job openings they qualify for, drawn from a pool of 10 openings. Does this guarantee a perfect matching exists?
AYes — each applicant has 2 choices, and 2 ≥ 1 so Hall's condition is satisfied
BNo — Hall's condition depends on which specific jobs each applicant qualifies for, not just how many
CYes — there are more openings (10) than applicants (5), so matches are always available
DNo — bipartite matching only applies when all left vertices have degree at least 3
Hall's condition must be checked for every subset S of left vertices, not just for individual vertices. Even though each applicant has 2 options, it is possible that all 5 applicants are only interested in the same 2 jobs — in which case the subset S = {all 5 applicants} has |N(S)| = 2 < 5, violating Hall's condition and making a perfect matching impossible. The number of openings and individual degrees don't capture this 'too many applicants share the same options' failure.
Question 2 Multiple Choice
Hall's condition fails for some subset S of left vertices — specifically, S has 4 left vertices but only 3 distinct neighbors on the right. What can you conclude?
ANo matching of any kind exists in the graph
BA perfect matching from the left side is impossible, but a maximum matching may still include some left vertices
CThe graph cannot be bipartite if Hall's condition fails
DThe condition only shows that a perfect matching from the right side doesn't exist
Hall's theorem is specifically about perfect matchings from the left side (matching every left vertex). If the condition fails for S, those 4 left vertices cannot all be matched simultaneously since there are only 3 right vertices available for them. However, a maximum matching still exists — it may match 3 of those 4 vertices and all others where the condition holds. Hall's failure rules out 'everyone matched,' not 'anyone matched.'
Question 3 True / False
Hall's condition must be verified for every subset of left vertices — even a single subset violating the condition is sufficient to prove no perfect matching exists.
TTrue
FFalse
Answer: True
Hall's theorem is an 'if and only if' result: a perfect matching from the left side exists precisely when Hall's condition holds for ALL subsets. This means necessity runs both ways — if any single subset S has |N(S)| < |S|, you immediately know no perfect matching is possible, because those |S| left vertices cannot all find distinct mates. You don't need to check the rest of the graph once a violating subset is found.
Question 4 True / False
If nearly every left vertex in a bipartite graph has at least one neighbor on the right side, Hall's condition is automatically satisfied and a perfect matching should exist.
TTrue
FFalse
Answer: False
This is the most common misconception about Hall's theorem. Having at least one neighbor for each individual vertex only checks subsets of size 1. The condition can still fail for larger subsets. A simple counterexample: three left vertices all connected to the same single right vertex — each has a neighbor, but the subset {all three} has |N(S)| = 1 < 3, and no perfect matching exists. Hall's condition is collective, not individual.
Question 5 Short Answer
Why is Hall's condition 'collective' rather than 'individual'? Give a concrete example that shows why checking each left vertex individually is insufficient to guarantee a perfect matching.
Think about your answer, then reveal below.
Model answer: Hall's condition is collective because a perfect matching requires each left vertex to be assigned a *distinct* right vertex — sharing is not allowed. Checking individually only verifies that each vertex has some neighbor, not that the neighborhood structure allows all of them to be matched simultaneously. Example: 3 applicants (A, B, C) each qualified for exactly 1 job, and all three qualify for the same job J. Each has a neighbor, but the subset S = {A, B, C} has N(S) = {J}, so |N(S)| = 1 < 3 = |S|. No perfect matching exists — only one applicant can get job J.
The insight is that a perfect matching is a global combinatorial constraint. Local availability (each vertex has a neighbor) does not imply global feasibility (all can be matched simultaneously without conflict). Hall's theorem captures exactly what must hold globally — that no subset is 'too picky' — and proves that this necessary condition is also sufficient.