Раскраска ребер графа

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

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

Теорема 22. Плоский кубический 2-связный граф допускает правильную окраску граней четырьмя цветами тогда и только тогда, когда он допускает правильную окраску ребер в три цвета.

Доказательство. Так как по условию теоремы граф является 2-связным, то он не содержит точек сочленения и перешейков и каждое его ребро смежно ровно двум граням. Предположим, что грани этого графа правильно раскрашены четырьмя цветами a, ft у и S. Каждое ребро разделяет две грани, которые имеют различные цвета. Имеется 6 пар из четырех различных цветов: аД ау, а8, /3у, /38 и у8. Будем раскрашивать ребра графа в три цвета 1,2 и 3 по следующему правилу:

Докажем, что в результате мы получим правильную раскраску ребер. Действительно, предположим противное, что какие-то два смежных ребра а и Ь оказались одноцветными (напри- _р

мер цвета 1). Рассмотрим вершину А, инцидентную этим ребрам.

Так как граф является кубическим, то к вершине А примыкает ровно три грани gi, g2 и gj (см. рис. 131). К одной из этих граней (например, к gj) примыкают ребра а и Ь. Пусть грань g) покрашена цветом а. Тогда грани g_: и g₂ могут быть покрашены только цветом (3 (см. таблицу). Мы получили противоречие, так как, по условию, две смежные грани gi и g₂ не могут иметь одинаковый цвет.

Обратно, предположим, что ребра кубического графа правильно раскрашены в три цвета а, /3 и у. Тогда из каждой вершины выходит по одному ребру каждого цвета. Рассмотрим суграф G_a, полученный из исходного графа удалением всех ребер цвета а. Так как при этом из каждой вершины будет удалено ровно одно ребро, то граф G_a является однородным графом второй степени. По теореме о двух красках он допускает правильную раскраску граней в два цвета. Произведем правильную раскраску граней графа.

G_a цветами 1 и 2. Точно так же, удаляя из исходного графа все ребра цвета Д произведем правильную раскраску граней полученного суграфа Gp цветами 3 и 4. В результате каждая грань исходного графа будет покрашена дважды, сначала цветом 1 или 2, а затем цветом 3 или 4. Всего существует 4 комбинации пар цветов 1 и 3, 1 и 4, 2 и 3, 2 и 4. Итак, грани исходного графа раскрашены в четыре цвета: смесь 1 и 3, смесь 1 и 4, смесь 2 и 3 и смесь 2 и 4. Ясно, что полученная раскраска является правильной. Теорема доказана.