ПустьG – простой граф, пусть РG(К) – число способов, которым можно окрасить вершины графа G, используя К красок и соблюдая условие: никакие 2 смежные вершины не должны иметь один и тот же цвет. Пусть РG -хроматическая функция графа G.
Рассмотрим все возможные крайние случаи.
Пусть имеется граф: .i____.g____k., то РG(К)=К(К-1)² , т.к. среднюю вершину можно окрасить К способами и каждую из концевых вершин (К-1) способами. Всего (К-1)² способов. п-1