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