Изменения

* {{Лемма|statement=Каждый раз, когда нам надо искать вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что <tex>v_1v_i, v_2v_{i+1} \in E</tex>, такая вершина действительно существует.* После |proof=Рассмотрим множество <tex>S = \{i\mid v_1v_i \in E\}</tex>, состоящее из индексов вершин, смежных с <tex>v_1</tex>, и множество <tex>T = \{i+1 \mid v_2v_{i+1} \in E\}</tex>, индексов вершин смежных с <tex>v_2</tex>. Заметим, что <tex>S \subset \{3, 4, \ldots, n\}</tex>, а <tex>T \subset \{2, 3, \ldots, n - 1\}</tex>, тогда <tex>S\cup T\subset \{2, 3, \ldots, n(\} </tex>, а значит <tex>\left\vert S\cup T\right\vert \leqslant n - 1</tex>, в то же время <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} v_1 + \operatorname{deg} v_2 \geqslant n</tex> (по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]). Из этого следует, что <tex>S\cap T\ne \varnothing</tex> итераций между каждой парой соседних вершин очереди , а это и значит, что искомая вершина существует ребро.}}

Докажем первое. Рассмотрим множество {{Лемма|statement=После <tex>S = \{i\mid v_1v_i \in E\}n(n - 1)</tex>итераций между каждой парой соседних вершин очереди существует ребро.|proof=Достаточно заметить, состоящее из индексов вершинчто каждую итерацию алгоритма, мы, в случае отсутствия ребра, смежных с между <tex>v_1</tex>, и множество <tex>T = \v_{i+1 \mid v_2v_{i+1} \in E\2}</tex>, индексов увеличиваем количество пар соседних в очереди вершин смежных с <tex>v_2</tex>. Заметим, что <tex>S \subset \{3, 4, \ldots, n\}</tex>между которыми есть ребро, а как минимум на <tex>T \subset \{2, 3, \ldots, n - 1\}</tex>(это прямое следствие условия поиска нужной вершины, тогда в случае отсутствия ребра), для поиска такой пары требуется не более <tex>S\cup T\subset \{2, 3, \ldots, n\} </tex>, а значит итераций. Таких пар изначально не более <tex>\left\vert S\cup T\right\vert \leqslant n-1</tex>, в то же время <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} v_1 + \operatorname{deg} v_2 \geqslant n</tex> (по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]). Из этого откуда следует, что после <tex>S\cap T\ne \varnothingn</tex>итераций, а это и значит, что искомая вершина существуетвторое условие будет выполнено.}}

Для доказательства второй части, достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между <tex>v_1</tex> и <tex>v_{2}</tex> увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, как минимум на <tex>1</tex> (это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), для поиска такой пары требуется не более <tex>n</tex> итераций{Теорема|statement=Алгоритм находит гамильтонов цикл. Таких пар изначально не более <tex>n</tex>, откуда |proof=Из предыдущих лемм следует, что после <tex>n</tex> итераций, второе условие будет выполненокорректность алгоритма.}}