Задача
COM-B2-M08-P015 Совершенное паросочетание в регулярном графе
#15
★★★★☆ Уровень 4 из 5
Докажите, что в любом \(d\)-регулярном двудольном графе с \(d>0\) существует совершенное паросочетание.
Сначала докажите, что доли равны, затем примените Холла.
Пусть доли \(A\) и \(B\). Считая рёбра по долям, получаем \(d|A|=d|B|\), значит, \(|A|=|B|\).
По задаче о регулярном двудольном графе есть паросочетание, покрывающее \(A\). Так как доли равны, оно покрывает и \(B\). Следовательно, паросочетание совершенное.
Очень важный результат для графовых олимпиадных задач.