577
правок
Изменения
→Теорема Гуйя-Ури
тогда <tex>G</tex> {{---}} гамильтонов.
|proof=
Будем доказывать теорему от противного. Предположим, что это не так. Очевидно, что условие теоремы выполняется при <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>.
}}
