4.3. Дополнительный граф

Рассмотрим обыкновенный граф с вершинами. Дополнительный граф получается, если из полного (обыкновенного) графа с вершинами вычеркнуть все ребра, содержащиеся в исходном графе. Граф является самодополнительным, если он изоморфен своим дополнением. Так, например, граф на рис. 4.9 самодополнительный,

(см. скан)

Прежде чем предложить вниманию читателя интересную теорему о дополнительных графах, рассмотрим формулу Эйлера

и всегда выполняемые соотношения

(не очень полезное соотношение, но оно потребуется здесь),

Если подставить второе неравенство в формулу Эйлера, то получим

или Подставляя в формулу Эйлера и производя упрощения, получим неравенство которое справедливо для любого плоского графа. Следовательно, граф неплоский, если

Теорема 4.16. Если граф с вершинами и его дополнительный граф, то; (1) при по крайней мере, один из них плоский, (2) при по крайней мере, один из них неплоский, и (3) при первый или второй или сразу оба могут быть как плоскими, так и неплоскими.

Доказательство. Заметим, что для случая имеем где число ребер в Если то иначе

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

Доказательство для случаев 9 и 10 здесь не приводится из-за сложности. С помощью перебора можно показать [36 а], что при каждый плоский граф с ребрами имеет дополнительный граф, содержащий одни из двух подграфов Понтрягина — Куратовского. Отсюда также следует, что графу с вершинами и ребрами соответствует неплоский дополнительный граф, так как если мы удалим некоторую вершину вместе с инцидентными ей ребрами, то получим плоский граф с девятью вершинами, дополнительный граф которого в соответствии со сказанным является неплоским и содержится в дополнительном графе рассматриваемого графа с вершинами.

Прежде чем переходить к случаю рассмотрим граф для задачи с четырьмя пунктами обслуживания и четырьмя домами. Этот граф является неплоским, его дополнительный граф, очевидно, плоский. Снова рассмотрим подграф Понтрягина — Куратовского 2-го тина с двумя изолированными вершинами. Он содержит 9 ребер, а его дополнение — 19 ребер, что превышает 18, т. е. максимально возможное число ребер в плоском графе с восемью вершинами. В заключение рассмотрим два концентрических квадрата. Пометим вершины внутреннего квадрата числами 1, 2, 3, 4, а вершины внешнего квадрата числами 5, 6, 7, 8 так, чтобы вершина 5 являлась ближайшей к к 4. Пары вершин должны быть связаны прямыми ребрами и внешним ребром Полученный граф является плоским. Можно показать, что его дополнительный граф также является плоским.

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

Теорема 4.17. Если хроматические числа графа вершинами и его дополнительного графа

соответственно, то

Доказательство, Пусть -число вершин графа которые будут окрашены цветом, Тогда к

Две вершины одного цвета в связаны ребром в и, следовательно, будут окрашены в нем по-разному. Таким образом,

Теперь из

мы имеем

Это значит, что

С помощью индукции по покажем, что Теорема справедлива для Предположим, что она справедлива для вершин. Включим вершину в полный граф, получаемый объединением Так как связана с другими вершинами, то пусть из них, которые включены в образуют граф (с хроматическим числом которые включены в образуют граф (с хроматическим числом Очевидно, что для раскраски мы можем использовать самое большее один дополнительный цвет, кроме цветов, использованных в Таким образом,

Если действительно и вершина вместе с инцидентными ребрами в удаляется, то хроматическое число уменьшится. В этом случае откуда и снова

Таким образом, индуктивная часть доказательства закончена.

Наконец, из и из очевидно, следует, что

Теорема доказана.