Пример 2. Вычислим хроматическую функцию графа, состоящего из двух имеющих общую сторону треугольников

Рис. 4.3. Удаление ребра и склеивание двух вершин

С этой целью удалим ребро. Получим граф, показанный на рисунке 4.3 вторым. Он имеет q(q-1)(q-2)(q-1) правильных раскрасок. Но не все раскраски являются правильными для исходного графа. Число раскрасок, у которых концы удаленного ребра имеют одинаковый цвет, нужно вычесть. Число таких раскрасок равно значению хроматического многочлена графа, изображенного на рисунке третьим. Отсюда fG(q)= q(q –1)(q–2)(q–1) –q(q–1)(q–2).

Рассмотренный в примере 2 метод годится для вычисления fG(q) в общем случае:

Теорема 3. Хроматическая функция fG(q) конечного графа G с n вершинами является многочленом степени £ n.

Доказательство. По индукции по числу ребер m. При m=0 получаем fG(q)=qn . Пусть граф имеет m+1 ребер (и n вершин). Выбросим произвольное ребро g . Получится граф G’, хроматическая функция которого – многочлен степени n согласно предположению индукции. Чтобы получить число раскрасок исходного графа G, нужно из этого числа вычесть число раскрасок, при которых концы удаленного ребра g окрашены в одинаковый цвет. Это число раскрасок будет хроматической функцией графа G’’, полученного удалением ребра g и отождествлением концов этого ребра. Отсюда

fG(q)= fG(q) – fG ’’ (q) – разность многочленов степени £ n.