Задание 10. Докажите, что в дереве (в котором больше одной вершины) найдутся хотя бы две висячие вершины.

Рассмотрим в конечном дереве простой путь наибольшей длины. Его концы — висячие вершины.

Действительно, если бы у конца пути была соседняя вершина, не лежащая на пути, путь можно было бы продлить, что противоречит его наибольшей длине. Других соседей на самом пути у конца быть не может, кроме следующей вершины пути: иначе возник бы цикл, а дерево циклов не содержит. Значит, степень каждого конца равна 1.

Поскольку в дереве больше одной вершины, выбранный путь имеет два различных конца. Следовательно, в дереве есть как минимум две висячие вершины.