Lesson 6

To conclude the section, we reformulate Hall's theorem on representatives in terms of bipartite graphs and matchings.

Theorem (Hall, 1935). Let \(G(V_{1} \sqcup V_{2},E)\) be a bipartite graph. There exists a matching in \(G\) saturating part \(V_{1}\) if and only if \(|U| \le |N(U)|\) for any \(U \subseteq V_{1}\).