Теория:
Вспомним всё, что мы проходили в \(8\)-м классе, связанное с графами.
Дерево — это связный граф без циклов.
Пример:
Рис. \(1\). Пример дерева
Связность дерева (графа) означает, что из любой его вершины можно дойти по рёбрам до любой другой.
Теорема. Любые две вершины в дереве соединены единственной цепью.
Следствием этой теоремы служит следующее свойство.
Свойство \(1\). При удалении ребра из графа он перестаёт быть связным.
В любом дереве (в котором более одной вершины) есть концевая вершина.
Концевой или висячей вершиной называют вершину дерева, из которой выходит ровно одно ребро.
Свойство \(2\). Если в дереве конечное число вершин и есть хотя бы одно ребро, то в таком дереве есть концевая вершина.
Существует связь общего количества вершин дерева с количеством его рёбер.
Свойство \(3\). В дереве количество вершин на \(1\) больше числа рёбер.