112
правок
Изменения
Нет описания правки
|about=J. A. Bondy
|statement=
<tex>G = <V, E> </tex> {{---}} гамильтонов граф, <tex>|V| = n, |E| \geq geqslant n^2/4 </tex>.
Тогда верно одно из двух утверждений:
#<tex> G </tex> {{---}} панциклический граф
}}
Обозначим как <tex> C=v_1 v_2 v_3 \ldots v_n </tex> гамилтонов цикл в графе <tex> G </tex>. Для простоты расположим <tex> C </tex> на окружности, тогда ребра не принадлежащие <tex> C </tex> можно считать хордами.
Пусть в графе нет цикла длины <tex> l, 3 \leqslant l \leqslant n-1 </tex> (по условию в графе существует гамильтонов цикл, длина которого равна <tex> n </tex>). Рассмотрим две соседний вершины в <tex> v_i v_i+1 </tex>
<tex> j + l - 1 \leqslant k \leqslant j + l - 2 </tex> <br>
<tex> j + 2 \leqslant k \leqslant j + l - 2 </tex>
{{Теорема
