Доказательство
Рассмотрим дерево G(V, Е). Дерево — связный граф, следовательно, .
Далее от противного. Пусть . Тогда
2q = Уd(vi) > 2(р - 1) + 1 = 2р - 1.
Но q = р - 1, то есть 2q = 2р - 2. Имеем противоречие: 2р - 2 2 > 2р - 1.
Следствие 2. Каждая не висячая вершина свободного дерева является точкой сочленения.
Доказательство
Пусть G(V, Е) — дерево, vV и d(v) > 1. Тогда и, w V(u,v) E& (u, w) E. Граф G связен, поэтому существует цепь (и, w). Если v<и,w>, то имеем цикл v,<и,w> ,v, что противоречит тому, что G — дерево. Следовательно, и, w V <и,w> v<u, w> и по теореме 8.1.2 вершина v — точка сочленения.