[[Хроматический многочлен]] графа <tex>G</tex> <tex>P(G,x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}</tex>, где <tex>pt(G,i)</tex> — число способов разбить вершины <tex>G</tex> на <tex>i</tex> независимых множеств, <tex>n = |VG|</tex>.
|proof=
Найдём число Пусть в <tex>x</tex>-раскрасок раскраске графа <tex>G</tex>, в которых используется точно <tex>i</tex> цветов (.* <tex>1 \le i \le x</tex>). Для получения такой раскраски сначала выберем одним из <tex>pt(G,i)</tex> способов разбиение графа <tex>G</tex> на <tex>i</tex> независимых множеств, а затем одним из <tex>{x\choose i} i! = x^{\underline i}</tex> способов <tex>i</tex> упорядоченных цветов из <tex>x</tex>.
При * <tex>i > x</tex> число Число <tex>x</tex>-раскрасок графа <tex>G</tex>, в которых используется точно <tex>i</tex> цветов равно <tex>0</tex>, так же как и <tex>x^{\underline i}</tex>. Суммирование по <tex>i</tex> от <tex>1</tex> до <tex>n</tex> даёт полное число способов.
}}
== Литература ==
