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