Задача
COM-B2-M08-P007 Большие левые степени
#7
★★★☆☆ Уровень 3 из 5
В двудольном графе каждая левая вершина имеет степень не меньше \(3\), а каждая правая вершина имеет степень не больше \(3\). Докажите, что существует паросочетание, покрывающее всю левую долю.
Для \(S\) слева посчитайте рёбра из \(S\) в \(N(S)\).
Возьмём любое \(S\) в левой доле. Из \(S\) выходит не меньше \(3|S|\) рёбер. Все они входят в \(N(S)\), а каждая вершина из \(N(S)\) принимает не больше \(3\) таких рёбер. Значит, \(3|S|\le3|N(S)|\), откуда \(|N(S)|\ge |S|\).
Условие Холла выполнено, следовательно, есть паросочетание, покрывающее левую долю.
Шаблон «Холл через подсчёт рёбер».