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

Представим страну как граф, где вершины — города, а ребра — дороги между городами.

“Подвесим” наш граф за какую-либо вершину. На первом уровне у нас будет только одна вершина, за которую мы подвешиваем. На втором уровне у нас будут все вершины, в которые можно попасть из вершины на первом уровне. На третьем уровне будут все вершины, в которые можно попасть из вершин второго уровня, которых нет на предыдущих двух уровнях. На четвертом уровне будут все вершины, в которые можно попасть из вершин третьего уровня, которых нет на предыдущих трех уровнях.

Докажем, что все вершины лежат на этих уровнях. Пойдем от противного, пусть существует такая вершина, что не принадлежит ни одному из этих уровней. Но тогда путь из вершины, за которую мы подвешивали наш граф, до этой вершины будет иметь более промежуточных городов (потому что, по факту, на наших четырех уровнях лежат все вершины, до которых можно добраться из выбранной не более чем через промежуточных города). Противоречие с условием.

Теперь посчитаем, какое наибольшее количество вершин может быть в нашем подвешенном графе. На первом уровне находится только одна вершина. На втором уровне может находиться не более вершин, т.к. из вершины на первом уровне выходит не более ребер. Из каждой вершины на втором уровне на третий уровень уходит не более ребер, поскольку одно ребро уходит на первый уровень. Т.е. на третьем уровне вершин не более чем в раза больше, чем на втором, или же не более Аналогично вершин на четвертом уровне больше, чем на третьем, не более чем в раза, т.е. не более Тогда в сумме у нас не более вершины в графе. На языке задачи получаем, что в стране не более городов.