Доказательство

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

Пусть граф G = (V, E) не содержит циклов нечетной длины. Можно считать его связным, так как хроматическое число не зависит от числа компонент графа. Вершины u, v Î V будем называть четно соединимыми, если расстояние d(u, v) – четное. Покажем, что бинарное отношение четной соединимости на множестве V является эквивалентностью:

· рефлексивность выполняется, так как d (v, v) = 0 – четное число;

· симметричность выполняется, так как d (v, u) = d (u, v);

· транзитивность: если d (u, v) и d (v, w) – четные числа, то d(u, w) тоже четное число. Пусть L (u, v), L (v, w) и L (u, w) – кратчайшие простые цепи, соединяющие соответствующие вершины. Тогда по предположению длина замкнутого маршрута L (u, v) _° L (v, w) _° L (w, u), равная d (u, v) + d (v, w) + d (w, u), является четной (так как из замкнутого маршрута нечетной длины может быть выделен простой цикл нечетной длины, что противоречит предположению). Отсюда d (u, w) = d (w, u) – четное число.

Отношение четной соединимости разбивает множество V на классы эквивалентности таким образом, что две вершины четно соединимы тогда и только тогда, когда они попадают в один класс.

Вершины каждого класса попарно несмежные, иначе расстояние между ними равнялось бы единице, т.е. было бы нечетным.

Покажем, что количество классов не больше двух. Пусть классов эквивалентности больше двух и пусть r, s, t – представители трех из них. Так как d (r, s) + d (s, t) + d (t, r) – четное число, то хотя бы одно из входящих в него расстояний должно быть четным и, следовательно, соответствующие ему вершины вопреки предположению принадлежат одному классу. Следовательно, классов эквивалентности не больше двух: V = V₁ È V₂.

Раскраска всех вершин класса V₁ в цвет 1, а всех вершин класса V₂ в цвет 2 является правильной для графа G (двудольного графа), следовательно, g(G) = 2

Дата добавления: 2015-07-20