105
правок
Изменения
м
Дмитрий Мурзин переименовал страницу Проблема четырех красок в Проблема четырёх красок: Ёфикация
[[Файл:Раскраска_планарного_графа_в_4_цвета.png|230px|thumb|right|4-раскраска планарного графа]]
Теперь, если есть [[Укладка графа на плоскости|гранигрань]] образованные , образованная нашим планарным графом , не треугольникявляющаяся треугольником, мы можем добавлять ребра без внедрения новых вершин до тех пор, пока все грани не станут треугольниками. Если полученный граф является раскрашиваемым в не более чем <tex>4</tex> цвета, то и исходный граф раскрашиваем так же (так как удаление ребер не увеличивает хроматическое число). Поэтому достаточно доказать теорему для триангулированных графов, и без потери общности мы предполагаем, что граф триангулирован.
Для дальнейших рассуждений нам понадобится следующее утверждение:
{{Утверждение
|statement=В <tex>G~\nexists </tex> <tex>v \in V</tex> : <tex>deg(v) \leqslant 4</tex>
|proof=Если в <tex>G</tex> есть вершина степени <tex>3</tex>, то мы можем просто удалить ее из графа, раскрасить полученный граф в <tex>4</tex> цвета, вернуть удаленную вершину и покрасить ее в один из цветов, не занятых соседями. Ан0алогично Аналогично [[Хроматическое_число_планарного_графа#Раскраска_в_5_цветов|теореме Хивуда]] доказывается, что удалив вершину степени <tex>4</tex> также всегда можно раскрасить граф в <tex>4</tex> цвета.
}}
