Изменения

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

Рассмотрим двудольный граф. Начнем цикл в доли <tex> U </tex>. Нужно пройти по четному числу ребер, чтобы подняться вернуться в <tex> U </tex> снова. Следовательно, при замыкании цикла число ребер будет четным.

Пусть ненулевой граф <tex> G </tex> связен и не имеет циклов нечетной длины. Выберем произвольно вершину <tex> u </tex> и разобьем множество всех вершин на на два непересекающихся множества <tex> U </tex> и <tex> V </tex> так, чтобы в <tex> U </tex> лежали вершины <tex> v_0 </tex>, такие что кратчайшая цепь <tex>(u, v_0)</tex> была чётной длины, а в <tex> V </tex> соответственно вершины <tex>v_1</tex>, для которых длина цепи <tex>(u, v_1)</tex> - нечётная. При этом <tex> u \in U </tex>.

В графе <tex> G </tex> нет ребер <tex>ab</tex>, таких что <tex>a, b </tex> лежат одновременно в <tex> U </tex> и <tex>V</tex>. Поведем доказательство от противного. Пусть <tex>a, b \in V_0 U </tex>. Зададим <tex> P_0 </tex> - кратчайшая <tex> (u, a) </tex> цепь, а <tex> P_1 </tex>- кратчайшая <tex> (u, b) </tex> цепь. Обе цепи четной длины. Пусть <tex> u v_0 </tex> - последняя вершина цепи <tex> P_0 </tex>, принадлежащая <tex> P_1 </tex>. Тогда подцепи от <tex> u </tex> до <tex> v_0 </tex> в <tex> P_0</tex> и <tex>P_1</tex> имеют одинаковую длину (иначе бы противоречили выбору , пройдя по более короткой подцепи от <tex>u</tex> до <tex>v_0</tex> мы смогли бы найти более короткую цепь от <tex> u </tex> до <tex> a </tex> или от <tex> u </tex> до <tex> b </tex>, чем цепь <tex> P_0 </tex> и или <tex> P_1 </tex> ). А так как подцепи одинаковы, то чётность у них одинакова, а значит в сумме с ребром <tex> ab </tex> они образуют цикл нечётной длины, что невозможно.