Подвешивание, ранжирование, упорядочивание в графах

Рассмотрим граф, в котором вершинами будут города, а ребрами — дороги. Подвесим граф за вершину Для каждой вершины определим её глубину — наименьшую длину пути до этой вершины из Назовём уровнем множество вершин одной глубины. Заметим, что вершина глубины может быть соединена ребром только с вершинами глубин или так что если глубины вершин отличаются хотя бы на 3, то у них нет общих соседей. Предположим, что есть вершина глубины более чем 63. Тогда рассмотрим вершины

где глубина будет Каждая из этих вершин имеет степень хотя бы 93, причём их соседи не пересекаются, так что всего вершин хотя бы противоречие. Значит, из до любой другой вершины можно добраться с не более чем 62 пересадками. Из независимости выбора получаем требуемое в условии.