Солнечная страна

[Roman Kotyk]

В Солнечной стране есть $2007$ городов, некоторые из них соединены дорогами так, что любые два города соединяет не больше, чем одна дорога. Оказалось, что с каждого города выходит не меньше, чем $3$ дороги. Доказать, что существует $k \le 16$ городов $A_1, A_2, ...,A_k$, которые образуют кольцевую дорогу, то есть с города $A_1$ есть дорога в $A_2$, с $A_2 -$ в $A_3$, ..., с последнего $A_k$ есть дорога в первый город $A_1$.

[slavav]

$k\le18$ доказывается сравнительно легко.

[Roman Kotyk]

slavav в сообщении #1081815 писал(а):

$k\le18$ доказывается сравнительно легко.

Напишете доказательство?

[slavav]

Так как число вершин нечётное, то есть вершина чётной степени. Следовательно, есть вершина степени 4 или больше.
Предположим, что нет циклов длины 18 или меньше. Тогда запустим поиск в глубину на девять рёбер из найденной вершины. Этот поиск перечислит какие-то вершины. Каждую вершину он перечислит не более одного раза (иначе мы бы получили "короткий" цикл). Сколько таких вершин? Их не меньше чем в четырёх двоичных деревьях высоты 9. То есть число вершин в графе не меньше, чем $1 + 4(2^9 - 1)$. А это 2045. Противоречие с заданным числом вершин в графе.