Визначення. Граф G з хроматичним числом χ (G) = 2 називається біхроматичним.
Теорема. Граф G двудолен ↔ G є біхроматична граф.
Необхідність →. нехай G = (V1, V2, E) є двочастковий граф. Вершини з V1 забарвимо в один колір, а вершини з V2 в інший. Отримана розфарбування вершин - правильна, бо сусідні розфарбовані вершини, одна з V1, інша з V2, пофарбована в різні кольори. Отже, граф є біхроматична.
← Достатність. Нехай G є біхроматична граф, тоді безліч його вершин можна розбити на два класи:
V1 - вершини з G, пофарбовані в один колір.
V2 - вершини з G, пофарбовані в інший колір.
Ребра з G можуть з'єднувати вершини тільки з різних класів → граф G = (V1, V2, E) - двудолен.
Зауваження. Наступні твердження еквівалентні:
1) Граф G біхроматична.
2) Граф G двудолен.
3) Всі прості цикли в G мають парну довжину.
Дерево є біхроматічний граф, бо вершини парних ярусів графа можна розфарбувати в один колір, а непарних ярусів в інший.
Затвердження. Нехай Kp є повний граф з p вершинами, тоді χ (Kp) = p.
Доведення. Індукцією по p.
Базис: p = 3 (трикутник), χ (K3) = 3.
Припущень індукції: припустимо, що χ (Kp-1) = p-1 фарб.
Крок: Покажемо, що χ (Kp) = p. Справді, нехай v є деяка вершина в Kp. Видалимо вершину v з Kp разом c належать їй ребрами. Тоді граф Kp - v = Kp-1 p-1-розфарбовуємо за припущенням індукції p-1 фарбами. 1,2,3 ... p-1. Вершина v в Kp може бути раскрашіваема тільки новою фарбою p. Тому χ (Kp) = p. Крок індукції встановлений. Затвердження: доведено.
Слідство. Існує граф зі як завгодно великим хроматичним числом (повні графи).
Слідство. Існує граф зі як завгодно малим хроматичним числом (порожні графи).