подграфов графа G, а через ? ( G) - мінімальну зі ступенів вершин графа G.
Теорема 1.Для будь-якого графаG вірно нерівність
В
Доказ. Твердження теореми очевидно для порожніх графів. Нехай G-довільний - хроматичний граф, , а - його мінімальний породжений підграф, що задовольняє умові . У цьому випадку для будь-якої вершини графа .
Припустимо, що . Граф правильно розфарбуємо квітами. Офарбивши потім вершину в один з цих кольорів, не використаний при фарбуванні суміжних з нею вершин, отримаємо правильну - розмальовку графа . Отже, і
В
Позначимо через найбільшу зі ступенів вершин графа .
Теорема 2.Просто граф - - розмальовують.
.
Доказ. Дано різних кольорів, отримаємо - розмальовку графа G таким чином.
Візьмемо довільну вершину і присвоїмо їй будь-який з квітів. Потім виберемо нераскрашенную вершину, наприклад . Привласнимо вершині колір, який не був привласнений суміжним з нею вершин. Це завжди можливо, оскільки і, отже, вершин, суміжних з вершиною , буде присвоєно найбільше, - квітів. Повторимо цей процес до тих пір, поки не розфарбувати всі вершини. В результаті вийде правильна - розмальовка. ?
Очевидно, що для повних графів і циклів непарної довжини. Дуже цікаво те, що для всіх інших графів . Цей результат отримано Бруксом [9] і доводиться нижче. Приводиться тут доказ запропонували Мельников і Візінга [11]. Інше доказ можна знайти в роботі [10].
Теорема 3 (Брукс). Нехай G - зв'язний простий граф. Якщо він не цикл непарної довжини і не повний граф, тобто коли G не містить в якості компонент граф або і цикл непарної довжини є компонентою G, то
Доказ...
