Расстоянием между двумя произвольными вершинами дерева будем называть длину простого...
Расстоянием между двумя произвольными вершинами дерева будем называть длину простого пути, соединяющего их. Удалённостью вершины дерева назовём сумму расстояний от неё до всех остальных вершин. В дереве есть две вершины с удалённостями, отличающимися на 1. Сколько в нем может быть вершин?

Предыдущий
вопрос Следующий
вопрос

Пусть в дереве есть вершины с удаленностями k и k+1. Пусть вершина с удаленностью k имеет n1 соседей, вершина с удаленностью k+1 имеет n2 соседей. Тогда общее количество вершин в дереве не меньше чем n1 + n2 + 2 (два - сами вершины с удаленностью k и k+1).

Так как в дереве n вершин имеют n-1 ребер, то количество ребер в дереве равно n-1.

Рассмотрим все вершины кроме вершин с удаленностями k и k+1. Каждая из этих вершин имеет удаленность не меньше чем k+1. Так как n1 вершина имеет k соседей, то количество этих вершин не менее чем kn1. Так как n2 вершина имеет k+1 соседей, то количество этих вершин не менее чем (k+1)n2.

Итак, получаем неравенство:
n >= k + 1 + k + n1 + (k+1) + n2 + kn1 + (k+1)n2.
n >= 4k + 2 + n1 + n2 + kn1 + (k+1)n2.

Поскольку n1 + n2 = n-2 (вершины кроме самих вершин с удаленностями k и k+1), то неравенство преобразуется в
n >= 4k + 2 + n-2 + k*(n-2).

Решая это уравнение получаем, что количество вершин в дереве не менее чем 3, что достигается, например, в случае линейного дерева из 3 вершин.