Олимпиада имени Леонарда Эйлера2014-2015 учебный год, II тур заключительного этапа

В стране Графинии $n$ $( n \geq 2)$ городов. Некоторые города соединены беспосадочными авиалиниями (по каждой авиалинии выполняются рейсы в обоих направлениях) таким образом, что из любого города можно самолётами (возможно, с пересадками) добраться до любого другого, но закрытие любой авиалинии нарушает это свойство. При этом из любого города выходит не больше $d$ авиалиний. Докажите, что все города Графинии можно разбить не более чем на $\frac{n}{2} + d$ групп таким образом, чтобы каждая авиалиния соединяла города из разных групп и для любых двух групп существовало не более одной авиалинии, соединяющей города из этих групп. ( Д. Карпов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Рассмотрим граф, где вершины — города, а рёбра — авиалинии. По условию он является деревом, вершины которого, как известно, можно занумеровать двумя цифрами так, чтобы любые две смежные вершины были отмечены разными цифрами. Сделаем это и покрасим в чёрный цвет вершины, отмеченные той цифрой, которой отмечено не меньше половины всех вершин. Остальные вершины покрасим в разные цвета, для этого хватит $n/2$ цветов. Докажем индукцией по количеству вершин, что черные вершины любого дерева, у которого степени всех вершин не превосходят $d$, можно перекрасить в $d$ цветов так, чтобы две вершины, имеющие общую соседнюю, были разноцветными. Так как $n \geq 2$, у дерева есть не чёрная вершина $x$. Пусть $y_1, \dots, y_k$ — соседи вершины $x$, они черные и $k \leq d$. Тогда при удалении вершины $x$ получается $k$ деревьев, каждое из которых меньше исходного и может быть покрашено по предположению индукции. Так как покраски этих деревьев независимы, можно покрасить их так, чтобы все вершины $y_1, \dots, y_k$ имели разные цвета, что нам и нужно. Вернемся к задаче и покрасим черные вершины нашего дерева, как сказано выше. Предположим, что пары соседних вершин $a_1b_1$ и $a_2b_2$ имеют одинаковые наборы цветов. Тогда не чёрные вершины $a_1$ и $a_2$ в этих парах совпадают. Но все соседи вершины $a_1$ разноцветны, противоречие.