Задача
COM-B2-M07-P010 Двудольный граф без нечётных циклов
#10
★★★☆☆ Уровень 3 из 5
Докажите, что в двудольном графе не существует цикла нечётной длины.
Вдоль цикла доли должны чередоваться.
Пусть граф разбит на доли \(A\) и \(B\), и каждое ребро соединяет вершину из \(A\) с вершиной из \(B\). При движении по циклу вершины по очереди попадают то в \(A\), то в \(B\). После нечётного числа шагов мы оказались бы в другой доле, а для замыкания цикла нужно вернуться в исходную вершину и исходную долю. Значит, длина цикла чётна.
Одна половина критерия двудольности.