Изменения
→Многочлен Татта полного графа
|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>
Понятно, что ребро <tex> (j_1, j_2) \in T </tex> не может быть ''внутренне'' активным, так как <tex> (0, j_1) \prec (j_1, j_2) </tex>, <tex> (0, j_2) \prec (j_1, j_2) </tex> и <tex> T \backslash (j_1, j_2) \cup {(0, j_1)} \in S_n</tex>, <tex> T \backslash (j_1, j_2) \cup {(0, j_2)} \in S_n</tex>. Также ребро <tex> (0, k) \in T </tex> внутренне активно в <tex> T </tex> <tex> \iff Leftrightarrow </tex> <tex> a = 0 </tex>, потому как если существует такая вершина <tex> j \in T'' </tex>, такая что <tex> j < k </tex>, то <tex> (0, j) \prec (0, k) </tex> и <tex> T \backslash (0, k) \cup {(0, j)} \in S_n</tex>. Таким образом равенство 1. доказано. <br>Рассмотрим <tex> (j_1, j_2) </tex>, где <tex> j_1 \in T' </tex>, <tex> j > 0 </tex> и <tex> j_2 \in T'' </tex>. Тогда <tex> (j_1, j_2) </tex> не может быть ''внешне'' активным, так как <tex> (0, k) \prec (j_1, j_2) </tex> и <tex> T \backslash (j_1, j_2) \cup {(0, k)} \in S_n </tex>. Аналогично, пусть <tex> j \in T'' </tex>, тогда ребро <tex> (0, j) </tex> - внешне активно <tex> \iff Leftrightarrow <\tex> <tex> j < k <\tex>. Таким образом мы доказали и второе утверждение.<br>
Теперь необходимое тождество для полинома Татта полного графа может быть получено при подстановке равенств (1) и (2) в <tex>
F_n(x, y) = \sum\limits_{T \in S} x^{i(T)}y^{e(T)}
</tex> и суммировании по всем парам поддеревьев <tex> T', T''</tex> и всем рёбрам типа <tex> (0, k) </tex>. ч.ит.д.
}}
