Изменения

Будем доказывать теорему от противного. Предположим, что это не так. Очевидно, что условие теоремы выполняется при <tex>n = 2</tex> и <tex>n = 3</tex>. Тогда существует орсвязный граф <tex>G</tex> с <tex>n \geqslant 4</tex>, который удовлетворяет условию и при этом не является гамильтоновым. Пусть <tex>C</tex> {{---}} максимальный цикл в <tex>G</tex> длины <tex>k</tex>. По лемме о длине цикла и по предположению о том, что граф не является гамильтоновым, получаем соотношение <tex>1 + n/2 \leqslant k < n</tex>. Теперь рассмотрим <tex>P = v_0 \dots v_l</tex> {{---}} путь максимальной длины в <tex>G</tex> такой, что никакая вершина этого пути не принадлежит циклу <tex>C</tex>. Предположим, что длина этого пути <tex>l \geqslant 0</tex>. Тогда <tex>k + l + 1 \leqslant n</tex>. Следовательно, <br><tex>l \leqslant n - k - 1 \leqslant n - (1 + n/2) - 1 \leqslant n/2 - 2</tex>. <br>Таким образом, <tex>l \leqslant n/2 - 2</tex>.