Следствие 1. Граф k5 не плоский.
Доказательство.ГрафK5, приведенный слева на рисунке 4.9, имеет 5 вершин и 10 ребер. Неравенство 103∙5 – 6 неверно, значит он не плоский.
Рис. 4.9. Графы K5 иK3,3
Следствие 2. Граф k3,3 не плоский.
Доказательство.В графеK3,3 , приведенном справа на рисунке 4.9, нет циклов длины 3. Отсюда в случае существования вложения в сферу каждая грань будет иметь не менее 4 ребер. По лемме, в этом случае имеет место неравенствоq 2p –4. Так как неравенство 92∙6 – 4 неверно, то графK3,3 не плоский.
Следовательно, обе задачи неразрешимы.
Следующая теорема Куратовского характеризует плоские графы.
Теорема 3. Граф плоский тогда и только тогда, когда он не содержит ни графа гомеоморфного K5 , ни графа гомемоморфного K3, 3 .
Раскраска плоского графа. Следующий вопрос – о раскраске плоских графов. В 1878 году эта проблема была поставлена Кэли на заседании Лондонского математического общества. Задана карта, состоящая из областей на сфере, которые можно интерпретировать как страны, расположенные на земной поверхности. Можно ли произвольную такую карту раскрасить в четыре цвета так, чтобы любые две имеющие общую границу страны были окрашены в различный цвет?
Положительное решение этой проблемы было опубликовано в 1977 году Аппелем и Хакеном.
Мы докажем, что пять цветов достаточно для раскраски любой карты. Метод доказактельства был предложен А.В. Кэмпе, и долгое время считалось, что этот метод годится и для четырех красок. Но это мнение было опровергнуто в 1890 году Хивудом.
Задача сводится к правильной раскраске вершин плоского графа, вершины которого соответствуют странам, а соединение вершин ребром осуществляется при наличии общей границы у стран.
Лемма 2. Пусть (V,e) – плоский конечный граф. Тогда существует вершина VV такая, что d(V) 5. Здесь d(V) – степень вершины V.
Доказательство.Иначе2q = d(v) 6p, иq3p, а мы доказали раньше, чтоq 3p – 6.
Теорема 4. Для плоского связного графа существует правильная раскраска вершин в 5 цветов.
Доказательство.Дляp5теорема верна. Пусть дляp – 1вершин теорема доказана. Рассмотрим граф сpвершинами. Найдем в нем вершинуvсd(v) 5. Обозначим через[v]подграф, полученный удалением вершиныvи инцидентных ей ребер. Существует правильная раскраска графа[v]. Наша задача – раскрасить вершинуv. Еслиd(v) < 5, то вершинуvраскрасим цветом, которого нет у смежных сvвершин. Пустьd(v)=5и пусть все смежные сvвершины раскрашены в различные цвета. Обозначим через13 подграф (рис. 4.10) графа[v], состоящий из вершин цвета 1 и 3. Если в нем
Рис. 4.10. К доказательству теоремы 4
нет путей между вершинами 1 и 3 из смежных с v, то компоненту связности вершины 3 перекрасим следующим образом: все вершины компоненты цвета 3 перекрасим в цвет
1, а все вершины компоненты цвета 1 – в цвет 3. Затем vпокрасим в цвет 3. Если в графе13существует путь, соединяющий вершины 1 и 3 и состоящий из вершин цвета 1 или 3, то в подграфе24нет пути между вершинами, смежными сv. В этом случае перекрасим вершины компоненты содержащей 4, аналогично тому, как это делалось выше: цвета 2 – в 4, а цвета 4 – в 2. Таким образом, если граф имеетpвершин, то для него существует правильная раскраска пятью красками. Теорема доказана.
Платоновы тела. Многогранник, у которого грани имеют одинаковое число сторон, и в каждой вершине сходится одинаковое число ребер, называетсяправильным. На рис. 4.11 приведены 5 правильных многогранников.
Рис. 4.11. Пять тел Платона
Следующее приложение эйлеровой характеристики – доказательство того, что правильные многогранники исчерпываются телами Платона. Рис. 4.11 показывает, что по крайней мере 5 правильных многогранников существует.