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