editor
177
правок
Изменения
м
→Коэффициенты хроматического многочлена
'''Индукционный переход''' (<tex>n \to n+1)</tex>:<br/>
Предположим, что теорема верна для всех графов на <tex>n</tex> вершинах. Рассмотрим графы на <tex>n+1</tex> вершине.
Индукционный переход будем доказывать индукцией по количеству ребер графа <tex>G</tex>. Если <tex>G</tex> не содержит ребер, то есть <tex>G</tex> является <tex>O_{n+1}</tex>, то его хроматический многочлен <tex>P(G,x)=x^{n+1}</tex> обладает доказываемым свойством. Теперь предположим, что для всех <tex>(n+1,m)</tex>-графов теорема верна. Возьмем <tex>(n+1,m+1)</tex>-граф <tex>G_{1}</tex> и его ребро <tex>uv</tex>. Обозначим за <tex>G</tex> граф, полученный из <tex>G_{1}</tex> удалением ребра <tex>uv</tex> (<tex>G=G_{1}-uv</tex>), а за <tex>G_{2}</tex> — граф, полученный из <tex>G_{1}</tex> «слитием» слиянием вершин <tex>u</tex> и <tex>v</tex>. Тогда из рекуррентной формулы следует:<br/>
<tex>P(G_{1},x)=P(G,x)-P(G_{2},x)</tex>.
Так как <tex>G</tex> — <tex>(n+1,m)</tex>-граф, а в <tex>G_{2}</tex> — <tex>n</tex> вершин, то для <tex>G</tex> и <tex>G_{2}</tex> теорема верна:<br/>
