Подвешивание, ранжирование, упорядочивание в графах

Пусть граф двудольный. Тогда в каждом цикле доли чередуются, причём начинаем и заканчиваем мы в одной и той же доле. Значит, цикл имеют чётную длину.

Теперь пусть все циклы имеют чётную длину. Будем считать граф связным. Подвесим граф за вершину Для каждой вершины определим её глубину — наименьшую длину пути до этой вершины из Пусть первая доля состоит из всех вершин чётной глубины, а вторая — из вершин нечётной глубины. Предположим, что внутри одной доли между вершинами и возникло ребро. Тогда по построению между и есть путь чётной длины, а между и путь также чётной длины. Тогда образуют цикл нечётной длины, противоречие.