|
|
 |
Условие
В стране 2001 город, некоторые пары городов соединены дорогами, причём из каждого города выходит хотя бы одна дорога и нет города, соединённого дорогами со всеми остальными. Назовём множество городов D доминирующим, если каждый не входящий в D город соединён дорогой с одним из городов множества D. Известно, что в каждом доминирующем множестве хотя бы k городов. Докажите, что страну можно разбить на 2001 – k республик так, что никакие два города из одной республики не будут соединены дорогой.
Решение
Рассмотрим граф, вершины которого соответствуют городам, а рёбра – дорогам. Требуется покрасить вершины этого графа в 2001 – k цветов так, что никакие две вершины одного цвета не соединены ребром (такая раскраска называется правильной).
Рассмотрим вершину A наибольшей степени, пусть из этой вершины выходит s рёбер (s < 2000). Обозначим через V множество из s вершин, соединённых с A, пусть W – множество из 2000 – s оставшихся вершин. Рассмотрим два случая.
1) В множестве W есть две соединённые ребром вершины B и C. Тогда рассмотрим множество U, состоящее из вершины A и всех вершин множества W, кроме C. В этом множестве 2000 – s вершин и каждая не входящая в U вершина соединена ребром с одной из вершин множества U (либо с вершиной A, либо с B). Следовательно, 2000 – s ≥ k.
Теперь вершины графа можно по очереди покрасить в s + 1 цвет так, чтобы никакие две вершины одного цвета не были соединены ребром (вершину нельзя красить в цвета её соседей, которых не более чем s, а в нашем распоряжении s + 1 цвет). Неравенство s + 1 = 2001 – (2000 – s) ≤ 2001 – k завершает доказательство.
2) Никакие две вершины множества W не соединены ребром. Покрасим все эти вершины в цвет 1, в этот же цвет можно покрасить вершину A (она не соединена ребром ни с одной вершиной из W). Вершины из множества W должны быть соединены с вершинами из множества V (так как из каждой вершины выходит хотя бы одно ребро). Это означает, что среди вершин множества V есть две, не соединённые ребром (иначе в этом множестве есть вершина, из которой выходит более s рёбер – к s – 1 остальным вершинам множества V, к вершине A и к вершине множества W). Так как среди s вершин множества V есть две, не соединённые ребром, вершины этого множества можно покрасить в s – 1 цвет.
Таким образом, все вершины оказались раскрашены в s цветов и никакие две вершины не соединены ребром. Так как все s вершин из множества V соединены ребром с вершиной A, то 2001 – s ≥ k, следовательно, s = 2001 – (2001 – s) ≤ 2001 – k, что и требовалось.
