Доказательство.

Повторим процедуру, описанную в теореме 7,выбирая несмежные вершины в G₁ и G₂ соединяя и отождествляя их, в результате получим 4 новых графа. Снова повторяем. Процесс заканчивается, когда каждый граф- полный.

Следствие из теоремы 7.

Если l=(V,W)-ребро простого графа G, то P(G,K)=P(G-l,k)-P(G*l,k)(3),где G-l-получается из G удалением ребра l, a G*l- замыкание вершин V и W и замена параллельных ребер одним ребром.

Если повторно применить формулу (2) к графу G, то процесс закончится на графах: Н₁,Н₂,. . . ,Н_k,поэтому P(G,K)=P(H₁,k)+P(H₂,k)+. . .+P(H_k,k);

Если использовать формулу (3), то процесс закончится на пустых графах без ребер => хроматический полином – множество комбинаций полиномов пустых графов.

 

Теорема Карона.

Граф G – двух раскрашиваемый тогда и только тогда, когда G- Эйлеров граф.

1)нижние оценки:

γ(G)≥ρ(G),

γ(G)≥, где n-число вершин

m- число ребер.

2)верхние оценки:

γ(G)≤1+max[P(x_i)+1]

x_i Є x