Изменения

Пусть ребро <tex> e </tex> является мостом. Тогда множество вершин <tex> V </tex> разбивается на два непересекающихся подмножества: <tex> V_1 </tex> и <tex> V_2 </tex>. Обозначим через <tex> G_1 </tex> и <tex> G_2 </tex> соответствующие подграфы. Их раскраски не связаны друг другом, поэтому <tex> \chi_{G \backslash e} (k) = \chi_{G_1} (k) \cdot \chi_{G_2} (k) </tex>. Далее, правильная раскраска <tex> G/e </tex> получается из правильных раскрасок <tex> G_1 </tex> и <tex> G_2 </tex>, где цвета склеиваемых вершин совпадают. Можно взять любую правильную раскраску <tex> G_1 </tex>, для чего есть <tex> \chi_{G_1} (k) </tex>, а из правильных раскрасок <tex> G_2 </tex> годится только доля <tex> \frac {1}{k} </tex>, где цвет склеиваемой вершины нужный. Таким образом, <tex> \chi _{G/e}(k) = \frac {1}{k} \chi _{G_1}(k) \chi _{G_2}(k) </tex>. Далее, по рекуррентному свойству [[Хроматический многочлен|хроматического многочлена ]] <tex> \chi _{G}(k) = \chi _{G \backslash e}(k) - \chi _{G / e}(k) = (1 - \frac {1}{k})\chi _{G_1}(k) \cdot \chi _{G_2}(k) = (k - 1)\chi _{G / e}(k) </tex>. Значит, <tex> P_G (k) = \frac {\chi _{G}(k)}{k^{|V|}} = \frac {(k - 1)\chi _{G / e}(k)}{k^{|V|}} = \frac {k - 1}{k} P_{G / e} (k) </tex>, то есть первое условие выполнено для <tex> x_0 = \frac {k - 1}{k} </tex>. <br>