Изменения
Нет описания правки
{{Теорема
|statement=
Пусть <tex>u</tex> и <tex>v</tex> - две несмежные вершины графа <tex>G</tex>. Если <tex>G_1=G+(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.
'''Следствие:'''
Хроматическая функция любого графа <tex>G</tex> равна сумме хроматических функций некоторого числа полных графов, порядки которых не превосходят порядка графа <tex>G</tex>.
Пусть <tex>G</tex> и <tex>G</tex> - смежные вершины графа <tex>G</tex>. Если <tex>G_1=G\(u,v)</tex> и <tex>G_2=G/(u,v)</tex>, то <tex>P(G,x)=P(G_1,x)-P(G_2,x)</tex>.
== Коэффициенты хроматического многочлена ==
{{Теорема
