Изменения

На <tex>k</tex>-ой итерации внешнего цикла рассматриваются вершины <tex>\mathrm{v}_k \mathrm{v}_{k+1}</tex>. Возможно 2 случаяДля доказательства корректности алгоритма достаточно показать:* между ними есть ребро, и тогда делать ничего не надо;* между ними ребра нетКаждый раз, и тогда когда нам надо найти такую искать вершину <tex>\mathrm{v}_jv_i</tex>, что где <tex>\mathrm{v}_k \mathrm{v}_j, \mathrm{v}_{k+1} \mathrm{v}_{j+1} \in \mathbb{E}i > 2</tex>;Покажем, такую что такая вершина обязательно найдется.Пусть <tex>S= \{ i| \mathrm{e}_i = \mathrm{v}_k \mathrm{v}_i \in \mathbb{E}\} \subset \{1, 2, ...v_1v_i,n\} \setminus \{k,k+1\} </tex> и <tex>T = \{ i| f_i=\mathrm{v}_k \mathrm{v}_v_2v_{i+1} \in \mathbb{E} \}\subset \{1, 2, ...,n-1\} \setminus \{k\} </tex>.Тогда <tex>S \cup T \subset \{1,2,...,n\} \setminus \{k\} </tex>, откуда <tex>|S \cup T |< n</tex>. Но <tex>|S|+|T| = \operatorname{deg}\ v_1 + \operatorname{deg}\ v_2 \ge n</tex> по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]], в зависимости от наших начальных условий. А значит <tex>S \cap T \ne \varnothing</tex>, следовательно искомая такая вершина обязательно найдетсядействительно существует.Теперь заметим, что после * После <tex>kn</tex>-ой итерации внешнего цикла итераций между всеми парами каждой парой соседних вершин <tex>\mathrm{v}_{i}, \mathrm{v}_{i+1}</tex>, где <tex>i \le k</tex> очереди существует ребро, а значит после <tex>n</tex> итераций мы найдем цикл.