Хроматичної число планарного графа

і суміжні їй вершини

Початок докази таке ж, як в попередній теоремі, труднощі виникають в індукційному переході. Покажемо що для випадку з -ю квітами все одно можна повернути вилучену вершину так, щоб розфарбування залишилася правильною.

Позначимо за - возвращаемую вершину, - вершину, пофарбовану в колір.

Якщо серед вершин, суміжних, є дві вершини одного кольору, значить залишається щонайменше один вільний колір, в який ми і пофарбуємо.

Інакше, укладемо отриманий після видалення граф на площину, повернемо вершину (поки безбарвну) і пронумеруємо кольору в порядку обходу суміжних вершин за годинниковою стрілкою.

Спробуємо пофарбувати в колір. Щоб розфарбування залишилася правильною, перефарбуємо суміжну їй вершину в колір. Якщо серед суміжних їй вершин є вершини, пофарбуємо їх в колір, і так далі. Розглянемо дві незвичайні ситуації, які можуть наступити під час обходу:

1. ми дійдемо до вже одного разу перефарбованій вершини (і хочемо перефарбувати її назад, що не вийде зробити). Видно що така ситуація неможлива, оскільки ми міняли кольори вершин за схемою, і якщо після закінчення обходу ми отримали дві суміжні вершини одного кольору, значить і до перекрасок в цьому місці були дві вершини однакового кольору, а за припущенням граф без був розфарбований правильно.
2. дійдемо до вершини, суміжній, початково мала колір, яку перефарбувати в не можна (тепер має колір).

Якщо цей процес був успішно завершений, то отримали правильне розфарбування. Якщо ж в Відповідно до другого варіанту перефарбування не вдалася, це означає, що в графі є цикл.

Тоді спробуємо таким же чином перефарбувати в колір, а суміжну їй в колір (з подальшими перефарбовування). Якщо вдасться - розфарбування отримана.

Якщо немає, то отримали ще один цикл. Але граф планарний, значить два отриманих циклу перетинаються крім вершини принаймні ще в одній, що неможливо, адже вершини першого циклу і другого - різних кольорів. Значить такий випадок наступити не міг.