Изменения
→Коэффициенты хроматического многочлена
Свободный член хроматического многочлена равен <tex>0</tex>.
|proof=
По определению хроматического многочлена для графа <tex>G</tex>, его значение в точке <tex>x</tex> равно количеству способов раскрасить вершины <tex>G</tex> правильным образом в <tex>x</tex> цветов. Очевидно, что количество Количество способов раскрасить граф в <tex>0</tex> цветов равно <tex>0</tex>. То есть <tex>P(G,0)=0</tex>. Из этого следует, что <tex>P(G,x)</tex> кратен <tex>x</tex>, следовательно его свободный член равен <tex>0</tex>.
}}
Применяя рекуррентную формулу повторно, хроматический полином можно представить в виде суммы хроматических полиномов полных графов, то есть:<br/>
<tex>P(G,x) = {P(K_{n},x) + a_{1}P(K_{n-1},x) + a_{2}P(K_{n-2},x) + \ldots = x^{\underline{n}} + a_{1}x^{\underline{n-1}}+a_{2}x^{\underline{n-2}}+\ldots}</tex><br/>
Из этой формулы очевидновидно, что хроматический многочлен имеет старший коэффициент, равный <tex>1</tex>.
}}
Индукция по количеству ребер.<br/>
'''База индукции:'''<br/>
Теорема очевидна верна для графа <tex>G</tex> из одной вершины, потому что <tex>P(G,x)=x</tex>.<br/>
'''Индукционный переход''' (<tex>n \to n+1)</tex>:<br/>
Предположим, что теорема верна для всех графов на <tex>n</tex> вершинах. Рассмотрим графы на <tex>n+1</tex> вершинах.
