Задача
COM-B2-M08-P003 Необходимость Холла
#3
★★☆☆☆ Уровень 2 из 5
Пусть в двудольном графе есть паросочетание, покрывающее всю левую долю \(A\). Докажите, что для любого \(S\subseteq A\) выполнено \(|N(S)|\ge |S|\).
Посмотрите, куда паросочетание отправляет вершины из \(S\).
Каждая вершина из \(S\) покрыта своим ребром паросочетания. Эти рёбра ведут в разные вершины правой доли, и все эти вершины лежат в \(N(S)\). Поэтому в \(N(S)\) есть как минимум \(|S|\) вершин.
Важно как половина теоремы Холла.