Замечание. Теорема Эйлера имеет место и для графов, не являющихся простыми

Хроматическое число графа

Определение 1. Раскраска вершин графа G=(V,E) называется правильной, если любые две смежные вершины окрашены в различные цвета. Минимальное число цветов, необходимое для правильной раскраски, называется хроматическим числом графа и обозначается c(G).

Теорема 1. Следующие свойства графа G равносильны

(1) c(G) £ 2;

(2) G - двудольный;

(3) каждый элементарный цикл в графе G имеет четную длину.

Доказательство. Равносильность (1) и (2) очевидна. Импликация (3) Þ (2) получается разбиением вершин, на вершины имеющие путь четной длины из фиксированной вершины, и имеющие путь нечетной длины. Импликация (2) Þ (3) очевидна.

Определение 2. Хроматической функцией f_G(q) графа G=(V,E) называется число правильных раскрасок с помощью £q красок.

Пример 1. Для дискретного графа G с n вершинами f_G(q)=qⁿ.

Вершина vÎV графа G=(V,E) называется висячей, если ее степень d(v) равна 1.

Теорема 2. Для дерева T имеющего число вершин n хроматическая функция равна f_G(q)=q(q – 1)^n-1.

Доказательство по индукции. Удалим висячую вершину (которая существует в силу формулы Эйлера и соотношения |E|+1=|V|). Получим дерево, которое можно раскрасить q(q-1)^n-2 способами, согласно предположению индукции. Затем снова присоединим удаленную вершину. Для каждой из q(q-1)^n-2 раскрасок ее можно раскрасить (q-1) способами. Отсюда получаем доказываемую формулу.