Двудольные графы и раскраска в 2 цвета

Определение:

Неориентированный граф [math]G = (W,E)[/math] называется двудольным, если множество его вершин можно разбить на две части [math] U \cup V = W , \mid U\mid \gt 0, \mid V\mid \gt 0[/math], так, что ни одна вершина в [math]U[/math] не соединена с вершинами в [math]U[/math] и ни одна вершина в [math]V[/math] не соединена с вершинами в [math]V[/math].

Пример двудольного графа

Так как множество вершин двудольного графа можно разделить на 2 независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества [math]\Rightarrow[/math] граф [math]G = (W,E)[/math] - 2-раскрашиваем. [math]\chi(G) = 2[/math].