Recipe

Check Hall's condition and find the deficiency

Use when: you have a bipartite graph and need to know whether every vertex in one side can be matched, or exactly how many cannot

Goal: either a confirmation that a matching saturating L exists, or the exact deficiency and the resulting maximum matching size when it doesn't

Taught in Hall's theorem, revisited

Quick recipe

Compute $N(S)$ for each subset of $L$ you test
Compare $|S|$ to $|N(S)|$ for every subset
Conclude a matching saturating $L$ exists
Compute the deficiency and the resulting max matching size

1
For every subset $S\subseteq L$ you check, find its neighborhood $N(S)$ : every vertex in $R$ reachable by some edge from a vertex in $S$ .

Example

Take $L=\{a,b,c\}$ , $R=\{x,y\}$ , with edges $a\text{-}x$ , $a\text{-}y$ , $b\text{-}x$ , $c\text{-}y$ . For $S=\{a,b\}$ : $N(S)=\{x,y\}$ , since $a$ reaches both $x,y$ and $b$ reaches $x$ .

Why: Hall's condition is a comparison against $N(S)$ , so it has to be computed before anything can be compared.
2
Check whether $|N(S)|\geq|S|$ holds for that same subset; a subset with $|N(S)|<|S|$ is a violation of Hall's condition.

Example

For $S=\{a,b,c\}$ in the graph above, $N(S)=\{x,y\}$ : $|S|=3$ exceeds $|N(S)|=2$ , a violation.
- $|N(S)|\geq|S|$ holds for every subset you test — Hall's condition holds; continue to Step 3.
- some subset has $|N(S)|<|S|$ — Hall's condition fails there; continue to Step 4 with that violating subset.
⚡ Shortcut

When several vertices in $L$ share the exact same neighborhood, test them together as one group instead of checking their subsets separately. A partial subset of such a group is never a tighter test than the whole group, since $N(S)$ stays fixed while $|S|$ only grows toward the full group.

Why: this comparison is the literal statement of Hall's condition, so it's the only test that decides the outcome.
3
Once $|N(S)|\geq|S|$ holds for every subset of $L$ , Hall's theorem guarantees a matching saturating all of $L$ exists, with no need to construct it by hand.

Example

For $L=\{a,b\}$ , $R=\{x,y,z\}$ , with edges $a\text{-}x$ , $a\text{-}y$ , $b\text{-}x$ , $b\text{-}z$ : every subset clears $|N(S)|\geq|S|$ , so a matching saturating both $a$ and $b$ exists.

Why: the flow-network cut argument shows every cut has capacity at least $|L|$ when the condition holds everywhere, forcing the max flow up to $|L|$ .
4
Take the worst violation found: the subset $S$ maximizing $|S|-|N(S)|$ . That value is $\operatorname{def}(G)$ , and the max matching size is $|L|-\operatorname{def}(G)$ .

Example

In the graph above, $S=\{a,b,c\}$ gives $|S|-|N(S)|=3-2=1=\operatorname{def}(G)$ , so the max matching size is $3-1=2$ .

Why: the deficiency theorem pins the maximum matching size exactly to $|L|-\operatorname{def}(G)$ , not merely "less than $|L|$ ."

Common mistakes

Stopping the subset search after checking only singletons; the worst violation often comes from a larger subset, as with $S=\{a,b,c\}$ above.
Forgetting that $S=\varnothing$ trivially satisfies $|N(S)|\geq|S|$ , so it's never the violating subset worth reporting.
Computing deficiency against $|R|$ instead of $|L|$ ; deficiency is always $|S|-|N(S)|$ for a subset $S\subseteq L$ .
Stopping at "no matching exists" instead of also reading off the deficiency, which the same violating subset already hands over.