Изменения

Перейти к: навигация, поиск

Проблема четырёх красок

Нет изменений в размере, 19:47, 26 ноября 2018
м
Общие идеи доказательства
[[Файл:Раскраска_планарного_графа_в_4_цвета.png|230px|thumb|right|4-раскраска планарного графа]]
Теперь, если есть [[Укладка графа на плоскости|гранигрань]], образованные образованная нашим планарным графом, не являющиеся являющаяся треугольником, мы можем добавлять ребра без внедрения новых вершин до тех пор, пока все грани не станут треугольниками. Если полученный граф является раскрашиваемым в не более чем <tex>4</tex> цвета, то и исходный граф раскрашиваем так же (так как удаление ребер не увеличивает хроматическое число). Поэтому достаточно доказать теорему для триангулированных графов, и без потери общности мы предполагаем, что граф триангулирован.
Для дальнейших рассуждений нам понадобится следующее утверждение:

Навигация