Hall's Marriage Theorem

Hall's theorem says a bipartite graph $G = (L, R, E)$ has a matching that covers all of $L$ if and only if for every subset $S \subseteq L$, the neighborhood $N(S)$ satisfies $|N(S)| \geq |S|$. Translation: every group of $k$ vertices in $L$ must have at least $k$ neighbors in $R$.

If this fails for any subset, no perfect matching exists. If it holds for all subsets, Kuhn's algorithm will find a perfect matching.