Задача
COM-B2-M07-P011 Раскраска по расстоянию
Пусть связный граф не содержит нечётных циклов. Выберите вершину \(v\). Докажите, что раскраска вершин по чётности расстояния от \(v\) задаёт двудольное разбиение.
Если ребро соединяет вершины одинаковой чётности расстояния, получите нечётный цикл.
Покрасим вершины с чётным расстоянием от \(v\) в одну долю, а с нечётным — в другую. Нужно доказать, что ребро не соединяет вершины одной доли.
Пусть ребро \(xy\) соединяет две вершины одинаковой чётности расстояний. Возьмём кратчайшие пути от \(v\) к \(x\) и от \(v\) к \(y\). У этих путей есть общий начальный участок; после его удаления остаются два пути одинаковой чётности суммарной длины. Добавив ребро \(xy\), получаем нечётный цикл. Это запрещено. Значит, каждое ребро соединяет разные доли.
Можно давать после обсуждения BFS-слоёв.