В дереве на 2021 вершине нет простого пути длины 6. Докажите, что в этом дереве есть вершина степени не меньше 33.

Предположим, что в этом дереве нет вершины, степень которой хотя бы 33.
Рассмотрим путь между двумя весячими вершинами $ v_1 $ и v6 (такие найдутся, т.к. граф дерево по
условию), длина которого равна 5. Обозначим вершины на этом пути, как $ v_2 $, $ v_3 $, $ v_4 $, $ v_5 $
По предположению из вершин $ v_2 $, $ v_3 $, $ v_4 $, $ v_5 $ исходит не более 32 ребер. Заметим, что из вершин, соединенных с $ v_2 $ и $ v_4 $ (помимо $ v_1 $, $ v_3 $, $ v_5 $, v6) не могут исходить ребра, т.к. тогда путь от вершин $ v_1 $ или
v6 до такой вершины будет длинне, чем 5. Тогда из вершин $ v_2 $ и $ v_4 $ в другие вершины (вершины,
помимо $ v_1 $, $ v_2 $, $ v_3 $, $ v_4 $, $ v_5 $, v6) ведет не более 2 ·30 = 60 ребер.
Теперь рассмотрим вершины $ v_3 $ и $ v_4 $. Из них в другие вершины(вершины, помимо $ v_1 $, $ v_2 $, $ v_3 $, $ v_4 $, $ v_5 $, v6)
ведет не более 2 · 30 = 60 ребер. Также из каждой вершины, соединенной с $ v_3 $ и $ v_4 $ исходит не более 32 ребер ⇒ из этих вершин ведет не более 31 · 30 ребер в другие вершины(вершины, помимо
$ v_1 $, $ v_2 $, $ v_3 $, $ v_4 $, $ v_5 $, v6).
Тогда всего в этом графе может быть не более, чем 6 (исходные) + 60(вершины из $ v_2 $ и $ v_4 $) + 2 · 30
· 31(вершины, соединенные с вершинами, соединенными c $ v_3 $ и $ v_4 $) + 2·30 (вершины, соединенные с
$ v_3 $ и $ v_4 $) = 1986 вершин. Но по условию их 2021 ⇒ исходное предположение неверно. Тогда найдется
вершина степени хотя бы 33.
Если же в графе нет простого пути длины 5, то в нем будет еще меньше вершин, чем 1986, то есть
меньше 2021 по условию – противоречие.