Hall obstruction
= Hall obstruction
{c}
{title2=$|N(S)|<|S|$}
A <Hall obstruction> is a left <subset> $S$ with fewer distinct <neighbours> than <vertices>. At most $|N(S)|$ members of $S$ can be matched, so at least $|S|-|N(S)|$ must remain unmatched. The <pigeonhole principle> proves failure without enumerating every proposed assignment.
For a stronger counterexample than an <isolated vertex>, take $L=\{a,b,c,d\}$ and $R=\{1,2,3,4\}$ with
$$
N(a)=N(b)=N(c)=\{1,2\},\qquad N(d)=\{3,4\}.
$$
Every <vertex> has positive <degree of a vertex>, the sides have equal <cardinality>, and $|N(L)|=|L|=4$. Every two-<vertex> left <subset> also passes the <Hall condition>. Nevertheless $S=\{a,b,c\}$ has only $N(S)=\{1,2\}$, so $2<3$ rules out <matching saturation> of $L$.
\Image[/hall-obstruction-three-jobs-two-slots.png]
{title=A three-<vertex> <Hall obstruction> has only two <neighbours>, despite enough slots in total}
{description=Red boundaries identify $S=\{a,b,c\}$ and $N(S)=\{1,2\}$. Thick blue <edges> give the maximum-size <matching in a graph> $\{a1,b2,d3\}$; $c$ and slot $4$ are unmatched.}
All sixteen left <subsets> can be checked by writing $k=|S\cap\{a,b,c\}|$ and $\varepsilon=1$ if $d\in S$, otherwise $0$. Then
$$
|S|=k+\varepsilon,\qquad |N(S)|=2\mathbf1_{\{k>0\}}+2\varepsilon.
$$
Only $k=3,\varepsilon=0$ violates the <Hall condition>. Every <matching in a graph> uses at most two <edges> incident to $\{a,b,c\}$ and at most one incident to $d$, so the <matching number> is three. There are exactly twelve size-three <matchings in a graph>: choose two of $a,b,c$ in three ways, assign them to $1,2$ in two ways, and choose $3$ or $4$ for $d$. Thus the obstruction identifies the bottleneck: adding availability only for $d$ cannot help; allowing $c$ to use slot $3$ permits $\{a1,b2,c3,d4\}$, a <perfect matching>.