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

Доказательство: Предположим противное: пусть в дереве с более чем одной вершиной не более одной висячей вершины (вершины степени 1). Рассмотрим самый длинный путь в дереве (путь, который нельзя удлинить, добавив новые вершины). Обозначим концы этого пути как A и B. Поскольку A – конец пути, она не может быть продолжена дальше по пути, и следовательно, она является висячей вершиной. Аналогично, B – тоже висячая вершина. Теперь предположим, что в дереве есть вершина C, отличная от A и B, которая является висячей. Тогда, если мы рассмотрим путь от A до C, он не может пересекаться с путем A-B, иначе мы можем удлинить путь A-B. Но это значит, что существует еще одна висячая вершина, что противоречит нашему предположению, что висячая вершина только одна. Таким образом, наше предположение неверно. В дереве всегда есть как минимум две висячие вершины.