Теорема 1. Граф является эйлеровым тогда и только тогда, когда нечетную степень имеют не более двух вершин.

Доказательство.Сначала доказывается, что существование содержащего все ребра замкнутого пути без кратных ребер равносильно четности всех вершин. Если граф эйлеров, то добавим ребро, соединяющее первую и последнюю вершину эйлерового пути. Получим, что все вершины дополненного графа имеют четные степени.

Пример1. Рассмотрим графы, приведенные на рис. 4.2 («открытое письмо» и «закрытое письмо») и проверим, являются ли они эйлеровыми. Поскольку граф, приведенный слева («закрытое письмо») имеет четыре вершины нечетной степени, то по теореме 1 он не будет эйлеровым. Значит, его невозможно нарисовать, не отрывая карандаш и проходя каждую линию ровно один раз. Граф, приведенный справа, имеет две вершины нечетной степени, следовательно, по теореме 1 он является эйлеровым, и его можно нарисовать, не отрывая карандаш и проходя каждую линию ровно один раз.

Рис. 4.2. Закрытое письмо и открытое письмо

4.2. Простые графы и их свойства

Ниже повсюду мы будем рассматривать простые графы. Они не имеют петель, у них между любыми двумя вершинами существует не более одного инцидентных им ребра. Иногда мы будем называть их просто графами.

Подграфомпростого графа (V,E) называется граф (V’,E’), такой, чтоV’V,E’E, и для всякого ребра={u,v}E’вершиныuиvпринадлежатE’.

Теорема 1. (Теорема Эйлера о сумме степеней вершин графа) Пусть d(v) обозначает степень вершины v. Для произвольного простого графа  =(V, E) верно соотношение .

Доказательство.Рассмотрим упорядоченные пары (v,), состоящие из вершиныvинцидентой ребру. Количество таких пар равно сумме степеней вершин. С другой стороны, оно равно удвоенному числу ребер.

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

4.3. Хроматическое число и хроматическая функция графа

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

Простой граф =(V,E) называетсядвудольным, если множество его вершинVможно разбить на два подмножестваV₁V₂=,V₁V₂=V, таких, что для каждого ребра его вершины принадлежат различным подмножествам.

На рис. 4.3 приведен пример двудольного графа. Верхние вершины составляют

Рис. 4.3. Пример двудольного графа

первое подмножество разбиения, а нижние – второе.

Пусть =(V,E) – простой граф. Напомним, что две вершины, принадлежащие одному ребру, называются смежными.

Определение 2. Элементарным путем длиныnв графе, соединяющим вершиныpиq, называется последовательность вершин (v₀, v₁,   , v_n) таких, что

• p=v₀и q=v_n ;

• v_iиv_i+1 смежны ,i{0,1,   , n1};

• v_i =v_j  i=j .

Определение 3. Элементарным цикломдлиныnв графеназывается последовательность вершин(v₀, v₁,   , v_n )таких, что

• v₀ =v_n ;

• v_iиv_i+1 смежны ,i{0,1,   , n1};

• v_i =v_j ( i=j  {i, j}={0, n} ).

Элементарный цикл можно интерпретировать как непрерывный замкнутый путь в графе, не имеющий кратных вершин.

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

1. ()2;

2.   двудольный ;

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

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

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

Определение 5.Граф называетсядискретным, если он не имеет ребер, т.е. состоит из одних вершин.

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

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

Определение 7.Простой граф, не имеющий элементарных циклов длиной больше нуля, называетсядеревом.

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

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

(q-1)способами. Отсюда получаем доказываемую формулу.

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

Число таких раскрасок равно значению хроматического многочлена графа, изображенного на рисунке третьим. Отсюда f_(q)= q(q –1)(q–2)(q–1) –q(q–1)(q–2).

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

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