Теорема 4. Для плоского связного графа существует правильная раскраска вершин в 5 цветов

Доказательство. Для p£5 теорема верна. Пусть для p – 1 вершин теорема доказана. Рассмотрим граф с p вершинами. Найдем в нем вершину v с d(v) £5. Обозначим через G[v] подграф, полученный удалением вершины v и инцидентных ей ребер. Существует правильная раскраска графа G[v]. Наша задача – раскрасить вершину v. Если d(v) < 5, то вершину v раскрасим цветом, которого нет у смежных с v вершин. Пусть d(v)=5 и пусть все смежные с v вершины раскрашены в различные цвета. Обозначим через G₁₃ подграф (рис. 4.10) графа G[v], состоящий из вершин цвета 1 и 3. Если в нем

Рис. 4.10. К доказательству теоремы 4

нет путей между вершинами 1 и 3 из смежных с v, то компоненту связности вершины 3 перекрасим следующим образом: все вершины компоненты цвета 3 перекрасим в цвет

1, а все вершины компоненты цвета 1 – в цвет 3. Затем v покрасим в цвет 3. Если в графе G₁₃ существует путь, соединяющий вершины 1 и 3 и состоящий из вершин цвета 1 или 3, то в подграфе G₂₄ нет пути между вершинами, смежными с v. В этом случае перекрасим вершины компоненты содержащей 4, аналогично тому, как это делалось выше: цвета 2 – в 4, а цвета 4 – в 2. Таким образом, если граф имеет p вершин, то для него существует правильная раскраска пятью красками. Теорема доказана.

Платоновы тела. Многогранник, у которого грани имеют одинаковое число сторон, и в каждой вершине сходится одинаковое число ребер, называется правильным. На рис. 4.11 приведены 5 правильных многогранников.

Рис. 4.11. Пять тел Платона

Следующее приложение эйлеровой характеристики – доказательство того, что правильные многогранники исчерпываются телами Платона. Рис. 4.11 показывает, что по крайней мере 5 правильных многогранников существует.

Теорема 5. Пусть p – число вершин, q – число ребер, r – число граней правильного многогранника. Тогда возможен один из следующих случаев, рассмотренных в таблице 4.1.

Таблица 4.1

Свойства тел Платона

Доказательство. Вершины графа, состоящего из ребер и вершин фиксированного многогранника имеют одинаковую степень. Обозначим эту степень через x. Пусть y – число сторон грани этого многогранника. Получаем систему уравнений

.

Так как x,y ³ 3, а в случае x,y ³ 4 имеет место неравенство , то возможны следующие случаи: x=3 или y=3.

Рассмотрим случай x=3:

.

Получаем

x =3, y =3, ;

x =3, y =4, ;

x =3, y =5, .

Аналогично x =4, x =5 при y =3.

Поиск по сайту: