Hall's marriage theorem (statement)

Theorem. A bipartite graph $G=(X,Y;E)$ has a matching that saturates every vertex of $X$ iff for every $S\subseteq X$, $|N(S)|\ge|S|$.

Example. $K_{n,n}$ satisfies the condition ($|N(S)|=|Y|=n\ge|S|$), so it has a perfect matching.

Non-example. Triangle $a,b,c$ with bipartition $X=\{a\}$, $Y=\{b,c\}$: trivially satisfiable. But $X=\{a,b\}$ in $C_4$ minus an edge: if $S=\{a,b\}$ and $N(S)=\{c\}$ (only one neighbor), condition fails.

Conclusion. Hall's condition is necessary and sufficient.