Задача
COM-B2-M08-P014 Неравные ограничения степеней
#14
★★★★☆ Уровень 4 из 5
В двудольном графе каждая левая вершина имеет степень не меньше \(5\), а каждая правая вершина имеет степень не больше \(4\). Докажите, что существует паросочетание, покрывающее левую долю.
Подсчёт даст даже \(|N(S)|\ge \frac54|S|\).
Для любого \(S\) слева из него выходит не меньше \(5|S|\) рёбер. Все эти рёбра входят в \(N(S)\), а каждая правая вершина принимает не больше \(4\) таких рёбер. Значит, \(5|S|\le4|N(S)|\), откуда \(|N(S)|\ge \frac54|S|\ge |S|\).
По теореме Холла есть паросочетание, покрывающее левую долю.
Хорошая олимпиадная версия «по степеням».