Theorem 4.6.1. Hall's Marriage Theorem.
Let \(G\) be a bipartite graph with sets \(A\) and \(B\text{.}\) Then \(G\) has a matching of \(A\) if and only if
\begin{equation*}
|N(S)| \ge |S|
\end{equation*}
for all \(S \subseteq A\text{.}\)
Let \(G\) be a bipartite graph with sets \(A\) and \(B\text{.}\) Then \(G\) has a matching of \(A\) if and only if
for all \(S \subseteq A\text{.}\)