Problem
COM-B2-M08-P003 Necessity of Hall
#3
★★☆☆☆ Level 2 of 5
Suppose a bipartite graph has a matching covering the whole left part \(A\). Prove that for every \(S\subseteq A\), \(|N(S)|\ge |S|\).
Look where the matching sends vertices of \(S\).
Each vertex of \(S\) is covered by its matching edge. These edges go to distinct vertices of the right part, and all these vertices lie in \(N(S)\). Therefore \(N(S)\) has at least \(|S|\) vertices.
Important as half of Hall's theorem.