Доказательство.

ÞПусть - двудольный граф, в котором существует цикл С_2п+1 нечетной длины. Пусть С_2п+1 = v₁ – v₂ – … – v_2n – v_2n+1 – v₁. Положим для определенности, что . Тогда , …, , , ребро (v₁, v_2n+1) соединяет вершины из одной доли – противоречие.

ÜПусть все простые циклы графа имеют четную длину. Граф

Рис. 14

будем считать связным, иначе каждую компоненту связности можно рассматривать отдельно. Разобьем вершины множества V на два непересекающихся подмножества V₁ и V₂ так.

1. Включим во множество V₁ произвольную вершину .

2. Выделим ярусы вершины: D(v, 0), D(v, 1), D(v, 2), …. Вершины ярусов D(v, 2k+1), k = 0, 1, 2, … включим во множество V₂. Вершины ярусов D(v, 2k), k = 1, 2, … включим во множество V₁.

Тогда V₁ V₂ = V; V₁ V₂ = Æ.

Предположим, что в графе есть вершины u и w, принадлежащие одной доле и соединенные ребром. Пусть для определенности u, w ; .

Рассмотрим геодезические, соединяющие вершину v с вершинами u и w. Обозначим их < v, u > и < v, w >, а их длины обозначим |< v, u >| и |< v, w >|. В силу сказанного |< v, u >| = 2п + 1, |< v, w >| = 2m + 1.

Эти геодезические имеют общие вершины, например, v. Пусть v¢ - наиболее удаленная от вершины v общая вершина геодезических (рис. 15). Может оказаться, что v¢ = v.

Рис. 15

Так как <v, v¢>₁ и <v, v¢>₂ – это участки геодезических, то и <v, v¢>₁ и <v, v¢>₂ – это геодезические, соединяющие вершины v и v¢. Значит, они имеют одинаковую длину, |<v, v¢>₁| = | <v, v¢>₂ | = k.

Тогда длина простого цикла u – w – < w, v¢ > – <v¢, u> равна

1 + (2n + 1 – k) + (2m + 1 – k) = 1+2m + 2n + 2 – 2k – нечетное число – противоречие.