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

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

Рис. 4.7. Пять платоновых тел

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

	p	q	r
Тетраэдр
Куб
Октаэдр
Додекаэдр
Икосаэдр

 

Доказательство. Вершины графа, состоящего из ребер и вершин фиксированного многогранника имеют одинаковую степень. Обозначим эту степень через 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.