Доказательство. Пусть G - дерево с n вершинами.
Согласно теореме 10.1 каждое ребро дерева является мостом. Удаление каждого моста, согласно определению 10.2, увеличивает количество компонент связности на 1.
Так как дерево - связный граф, то исходный граф G имеет одну компоненту связности. Удалив любое ребро, получаем 2 компоненты связности. Удалив 2 моста, имеем 3 компоненты связности. В общем случае, удалив i ребер, получаем i + 1 компоненту связности.
Итак далее, удалив все мосты, получаем n компонент связности
-изолированных вершин. Значит, процедуру удаления применяли к
n −1 мосту. Таким образом, в исходном графе G было n −1 ребро.
Остальные свойства деревьев сформулируем в следующей теореме, которая дается без доказательства.
Теорема 10.4. Для графа G с n вершинами следующие утверждения эквивалентны:
1.G - дерево;
2.G не содержит циклов и имеет n − 1 ребро;
3.G связен и имеет n − 1 ребро;
4.G связен и каждое его ребро является мостом;
5.G не содержит циклов, но добавление любого ребра приводит к образованию ровно одного цикла.
Следствие 10.4.1. В дереве, содержащем не менее двух вершин, по крайней мере две вершины являются висячими.
10.2Остовные деревья
Определение 10.3. Остовом (остовным деревом) графа G называется подграф T , являющийся деревом и содержащий все вершины графа G.