. Теорема очевидна для
Щоб довести теорему для , припустимо противне, тобто що існують графи, які не є повними, для яких і . Виберемо таке граф з мінімальним числом вершин.
Нехай , а - граф, отриманий в результаті видалення з графа вершини . З вибору графа G випливає, що - розмальовують. Отже, , інакше б для розмальовки вершини можна було використовувати один з? квітів, застосовуваних для розмальовки графа , що суперечить рівності . Іншим важливим наслідком є ​​наступне:
Властивість 1. У будь?-Розмальовці графа вершини, суміжні з вершиною , розфарбовуються по-різному.
Нехай - вершини, суміжні з вершиною . Нехай отримують у розфарбуванні графа кольору 1, 2, ...,? Відповідно. Позначимо через породжений підграф на вершинах, яким присвоєні кольору і .
Властивість 2. Вершини і знаходяться в одній компоненті зв'язності .
В іншому випадку, замінюючи кольору і в компоненті, яка містить , ми отримаємо нову?-розмальовку графа , в якій і присвоєно однаковий колір, що суперечить властивості 1.
Нехай - компонента , що містить вершини і .
Властивість 3. - шлях від вершини до вершини .
Припустимо, що ступінь в більше 1. Тоді суміжно не менше ніж з двома вершинами кольору . Оскільки у графі , ми можемо перефарбувати в колір < span align = "justify">, так що в вийшла нової розмальовці вершини і ...
