Изменения
→Раскраска в 6 цветов
Докажем по индукции.
* База
*: Если граф содержит не более <tex>6 </tex> вершин, то утверждение очевидно.
* Переход
*: Предположим, что для планарного графа с <tex>N</tex> вершинами существует раскраска в <tex>6 </tex> цветов. Докажем то же для графа с <tex> N+1 </tex> вершиной.*: По только что доказанной лемме в <tex> G </tex> найдётся вершина степени не больше <tex>5</tex>. Удалим её; по предположению индукции получившийся граф можно раскрасить в <tex>6 </tex> цветов. *: Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин (ведь "занято" максимум <tex>5 </tex> цветов). Индукционный переход доказан.
}}