Задача
COM-B2-M08-P019 Разложение на совершенные паросочетания
#19
★★★★★ Уровень 5 из 5
Докажите, что рёбра любого \(d\)-регулярного двудольного графа можно разбить на \(d\) совершенных паросочетаний.
Найдите одно совершенное паросочетание и удалите его.
В \(d\)-регулярном двудольном графе есть совершенное паросочетание. Удалим его рёбра. У каждой вершины степень уменьшится на \(1\), поэтому оставшийся граф будет \((d-1)\)-регулярным и двудольным.
Повторяем рассуждение: находим совершенное паросочетание, удаляем его. Через \(d\) шагов все рёбра будут удалены, а найденные паросочетания попарно не пересекаются и покрывают все рёбра.
Красивое применение Холла с индукцией.