Доказательство. Необходимость. ( ) Пусть задан неориентированный граф G=(V, U) , не имеющий петель, для которого c(G) = 2

Необходимость. () Пусть задан неориентированный граф G =(V, U), не имеющий петель, для которого c (G) = 2. Предположим, что в G имеются элементарные циклы нечетной длины.

Пусть С = v ₀,..., v _{2 k +1}, где v _{2 k +1} = v ₀, - элементарный цикл в G, имеющий нечетную длину.

Возьмем 2 -раскраску графа G. Тогда все вершины цикла С, имеющие четные номера, раскрашены в один цвет, а вершины этого же цикла с нечетными номерами раскрашены в другой цвет.

Вершины v ₀ и v _{2 k +1} цикла С совпадают и имеют четный и нечетный номера. Следовательно, одна и та же вершина графа должна быть раскрашена в разные цвета. Полученное противоречие означает, что предположение о существовании элементарных циклов нечетной длины в 2 -хроматическом графе G является неверным.

Поэтому G не может содержать элементарных циклов нечетной длины.

Достаточность. ()

Проведем доказательство в предположении связности графа G. Если G имеет несколько компонент связности, то проводимое доказательство справедливо для каждой компоненты связности этого графа, а значит, и для всего графа G.

Пусть связный граф G не имеет элементарных циклов нечетной длины.

Возьмем два цвета, которые обозначим как b и w.

Раскрасим все вершины G с помощью следующей процедуры.

1. Произвольную вершину v графа G раскрасим в цвет b.

2. Еще нераскрашенные вершины, соседние с вершинами, которые окрашены в цвет b, раскрасим в цвет w.

3. Все нераскрашенные вершины, которые являются соседними с вершинами, окрашенными в цвет w, раскрасим в цвет b.

4. Действия 2 и 3 повторяются, пока в G остаются не раскрашенные вершины.

Через конечное число шагов все вершины графа G будут раскрашены с использованием двух цветов.

Покажем, что выполненное раскрашивание вершин G является 2 -раскраской этого графа.

Предположим противное. В графе G некоторые соседние вершины v ₁ и v ₂ раскрашены одинаково.

Из определения процесса раскрашивания вершин графа G следует существование таких простых путей W ₁ и W ₂, ведущих из v в вершины v ₁ и v ₂, длины которых имеют одинаковую четность. Данная ситуация изображена на рис. 5.32.

v

W ₁ v ₃ W ₂

v ₁ v ₂

Рис. 5.32

На этом рисунке пунктирные линии представляют пути в G. Здесь v ₃-последняя общая вершина путей W ₁ и W ₂. Тогда последовательность вершин v ₃,..., v ₂, v ₁,..., v ₃ образует цикл нечетной длины. Это противоречит предположению об отсутствии таких циклов в графе G.

Поэтому приведенное раскрашивание G является его 2 -раскраской.