Теория:
Вспомним важное свойство дерева.
В дереве количество вершин на \(1\) больше числа рёбер.
Пример:
сколько рёбер в дереве, у которого \(15\) вершин?
Так как вершин у дерева на \(1\) больше, чем рёбер, значит, количество рёбер на \(1\) меньше количества вершин.
\(15 - 1 = 14\) рёбер.
Дерево представляет собой связный граф, в котором нет циклов. Это означает, что из любой его вершины можно дойти по рёбрам до любой другой. Значит, справедлива следующая теорема.
Теорема. Любые две вершины в дереве соединены единственной цепью.
Следствием этой теоремы служит следующее свойство.
Свойство \(1\). При удалении ребра из графа граф перестаёт быть связным.
Вспомним определение концевой вершины.
Вершина называется концевой, если из неё выходит ровно одно ребро.
Справедливо следующее свойство.
Свойство \(2\). Если в дереве конечное число вершин и есть хотя бы одно ребро, то в таком дереве есть концевая вершина.
Доказательство. Пусть все вершины будут иметь степень \(2\) или выше. Это означает, что в каждую вершину можно зайти по одному ребру и выйти из неё по другому, так как циклов нет.
Начнём путь с произвольной вершины и будем строить его без повторения рёбер.
По условию у нас конечное число вершин, значит, рано или поздно какая-то вершина повторится и мы получим цикл. Но в дереве циклов нет.
Получили противоречие. Значит, наше предположение неверно и в дереве есть вершины степени меньше \(2\). Вершин степени \(0\) нет, так как это нарушит связность дерева. Следовательно, найдётся вершина степени \(1\), которая является концевой вершиной.