Идея. Число рёбер дерева на 1 меньше числа вершин (свойство 3, §47*), сумма степеней вдвое больше числа рёбер. Концевая вершина имеет степень 1, остальные — не меньше 2 (степень 0 у дерева с рёбрами невозможна: граф связен).
1Для 100 вершин рёбер 99, сумма степеней 198. Все остальные оценки следуют из неё.
2Наибольшее число концов: если бы все 100 вершин были концевыми, сумма была бы 100, а нужно 198. Значит, неконцевая вершина есть, и концов не больше 99. Звезда — одна вершина, соединённая со всеми — это число даёт.
3Наименьшее число концов: пусть их k, тогда у остальных 100−k вершин степень не меньше 2, сумма степеней не меньше k+2(100−k). Она равна 198, отсюда k≥2. Цепочка вершин даёт ровно 2 конца.
Проверка. Тот же вывод для малого числа вершин: у дерева из 4 вершин концов от 2 до 3, то есть от 2 до n−1.
