мають однаковий колір, що суперечить властивості 1.
Аналогічно можна показати, що ступінь в дорівнює 1.
Ступінь всіх інших вершин дорівнює 2. Припустимо противне. Нехай - перша вершина ступеня (в ) більше 2 на шляху від вершини до вершини і . Якщо розфарбована в колір , то вона суміжно принаймні з трьома вершинами кольору . Оскільки , можна перефарбувати в колір , тому в новій розфарбовуванні вершини і будуть у різних компонентах, що суперечить властивості 2.
Таким чином, є шляхом з вершини в вершину .
Властивість 4. і не мають спільних вершин, за винятком .
Нехай - загальна вершина і . Тоді розфарбована в колір і суміжно принаймні з двома вершинами кольору і двома вершинами кольору . Так як , існує колір в який можна перефарбувати . Але це розділить вершини і , що суперечить властивості 2.
Продовжимо доказ теореми. Встановимо тепер протиріччя зі свойством4. p align="justify"> Оскільки - не повний граф на вершині, існують дві несуміжні вершини, наприклад і . Шлях містить вершину , суміжну з вершиною . Припустимо, що ми поміняли місцями кольори 1 і 3 у дорозі (який присутній, оскільки ), в результаті чого в новій розфарбовуванні вершина отримує колір 3, а вершина - колір 1. Але тоді нові компоненти а і містять загальну вершину , що суперечить властивості 4 .
Це завершує до...
