51
правка
Изменения
→Основные свойства
|id = lem1
|statement = Пусть существуют вершины <tex> y, z -</tex> соседи вершины <tex> x </tex>. Тогда <tex> 2d(x) < d(y) + d(z) </tex>.
|proof = Подвесим дерево за вершину <tex> x </tex>. Тогда дерево можно представить в виде объединения трёх непересекающихся множеств: <tex> Y, Z </tex> (поддеревья с корнем в вершинах <tex> y, z </tex> соответственно) и <tex> X - </tex> остальных вершин (заметим, что все эти множества не пустые, так как содержат вершины <tex> y, z, x </tex> соответственно). Найдём <tex> d(x) : </tex>:
<tex> d(x) = d(y) + |Y| - |Z| - |X| </tex>. Это верно, так как все вершины из множества <tex> Y </tex> находятся от <tex> x </tex> на одно ребро дальше, чем от <tex> y </tex>, а вершины из множеств <tex> Z, X </tex> наоборот. Аналогично <tex> d(x) = d(z) + |Z| - |Y| - |X| </tex>. Сложим эти уравнения и получим: <tex> 2d(x) = d(y) + d(z) - 2|X| </tex>. При этом <tex> |X| > 0 </tex>. Таким образом, <tex> 2d(x) < d(y) + d(z) </tex>.
}}
