Изменения
→Рекуррентные формулы для хроматических многочленов
{{Теорема
|statement=
Пусть <tex>u</tex> и <tex>v</tex> - несмежные вершины графа <tex>G</tex>. Если <tex>G_1=G+\cup(u,v)</tex>, а <tex>G_2</tex> получен из <tex>G</tex> слиянием вершин <tex>u</tex> и <tex>v</tex>, то <tex>P(G,x)=P(G_1,x)+P(G_2,x)</tex>.
|proof=
Рассмотрим все произвольные раскраски графа <tex>G</tex>. Рассмотрим те из них, при которых вершины <tex>u</tex> и <tex>v</tex> окрашены в разные цвета. Если добавить к графу <tex>G</tex> ребро <tex>(u,v)</tex>, то они не изменятся, то есть останутся правильными. Рассмотрим раскраски, при которых <tex>u</tex> и <tex>v</tex> одного цвета. Все эти раскраски останутся правильными и для графа, полученного из G слиянием вершин u и v.
