Изменения
→Раскраска в 2 цвета
{{Теорема
|statement=
[[Основные определения теории графов|Граф]] <tex>2-</tex>-[[Раскраска графа|раскрашиваемый]] тогда и только тогда, когда он [[Двудольные графы|двудольный]].
|proof=
Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф <tex>G = (W, E)</tex> — <tex>2-</tex>-раскрашиваем. <tex>\chi(G) = 2</tex>.
Если же граф <tex>2-</tex> -раскрашиваемый, то множество его вершин можно разделить на два непересекающихся множества так, чтобы в каждом из них не нашлось двух смежных вершин. Тогда граф будет двудольны.
}}
