Изменения
→Многочлен Татта полного графа
|proof=
Зафиксируем остовное дерево <tex> T \in S_n </tex>. Рассмотрим ребро <tex> (0, k) \in T </tex>, которое разбивает <tex> T </tex> на поддеревья <tex> T' </tex> и <tex> T'' </tex>, и при этом вершина 0 лежит в <tex> T'' </tex>. Пусть <tex> a = |\{j|j \in T \& j < k\}|</tex>. Тогда докажем следующие два утверждения:
# <tex> i(T) = i(T') + \delta _{a, 0} </tex>, где <tex> \delta _{a, 0} </tex> - символ Кронекера
# <tex> e(T) = e(T') + e(T'') + a </tex>
