|proof=
''Достаточность<tex>\Rightarrow</tex> Пусть ненулевой граф <tex> G </tex> [[k-связность|связен]] и не имеет циклов нечетной длины. Выберем произвольно вершину <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> U G </tex>. Нужно пройти по четному числу нет ребер<tex>ab</tex>, чтобы вернуться таких что <tex>a, b </tex> лежат одновременно в <tex> U </tex> снова и <tex>V</tex>. СледовательноДокажем это от противного. Пусть <tex>a, при замыкании цикла число ребер будет четнымb \in U </tex>. Зададим <tex> P_0 </tex> — кратчайшая <tex> (u, a) </tex> цепь, а <tex> P_1 </tex> — кратчайшая <tex> (u, b) </tex> цепь. ''НеобходимостьОбе цепи четной длины.'' Пусть ненулевой граф <tex> G v_0 </tex> — последняя вершина цепи <tex> P_0 </tex>, принадлежащая <tex> P_1 </tex> [[k-связность|связен]] и не имеет циклов нечетной длины. Выберем произвольно вершину Тогда подцепи от <tex> u </tex> и разобьем множество всех вершин на два непересекающихся множества до <tex> v_0 </tex> в <tex> U P_0</tex> и <tex> V P_1</tex> такимеют одинаковую длину (иначе бы, чтобы в пройдя по более короткой подцепи от <tex> U 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> v_0 </tex> до <tex> a </tex> и от <tex> v_0)</tex> была чётной длины, а в до <tex> V b </tex> соответственно вершины в цепях <tex>v_1P_0 </tex>, для которых длина цепи и <tex>(u, v_1)P_1 </tex> — нечётная. При этом имеют одинаковую четность, а значит в сумме с ребром <tex> u \in U ab </tex>они образуют цикл нечётной длины, что невозможно.
В графе <tex> G \Leftarrow</tex> нет ребер <tex>ab</tex>, таких что <tex>a, b </tex> лежат одновременно Рассмотрим двудольный граф. Начнем цикл в доле <tex> U </tex> и <tex>V</tex>. Докажем это от противного. Пусть <tex>a, b \in U </tex>. Зададим <tex> P_0 </tex> — кратчайшая <tex> (u, a) </tex> цепь, а <tex> P_1 </tex> — кратчайшая <tex> (u, b) </tex> цепь. Обе цепи четной длины. Пусть <tex> v_0 </tex> — последняя вершина цепи <tex> P_0 </tex>Нужно пройти по четному числу ребер, принадлежащая <tex> P_1 </tex>. Тогда подцепи от <tex> u </tex> до <tex> v_0 </tex> чтобы вернуться в <tex> P_0U </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> v_0 </tex> до <tex> a </tex> и от <tex> v_0 </tex> до <tex> b </tex> в цепях <tex> P_0 </tex> и <tex> P_1 </tex> имеют одинаковую четностьСледовательно, а значит в сумме с ребром <tex> ab </tex> они образуют цикл нечётной длины, что невозможнопри замыкании цикла число ребер будет четным.
}}
