 Hall obstruction

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\}$ withEvery 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$.

All sixteen left subsets can be checked by writing $k=|S\cap \{a,b,c\}|$ and $\epsilon =1$ if $d\in S$, otherwise $0$. ThenOnly $k=3,\epsilon =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.