Изменения

* Каждый раз, когда нам надо искать вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что <tex>v_1v_i, v_2v_{i+1} \in \mathbb{E}</tex>, такая вершина действительно существует.* После <tex>n * (n - 1)</tex> итераций между каждой парой соседних вершин очереди существует ребро.

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

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