71
правка
Изменения
→Доказательство алгоритма
Покажем, что такая вершина обязательно найдется.
Пусть <tex>S= \{ i| \mathrm{e}_i = \mathrm{v}_k \mathrm{v}_i \in \mathbb{E}\}
\subset \{1, 2, ...,n\} \setminus \{\mathrm{k},\mathrm{k+1}\}</tex> и <tex>T = \{ i| f_i=\mathrm{v}_2 _k \mathrm{v}_{i+1} \in \mathbb{E} \}\subset \{1, 2, 3, ...,n-1\} \setminus \{k\}</tex>.Тогда <tex>S \cup T \subset \{1,2,3,...,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>k</tex>-ой итерации внешнего цикла между всеми парами вершин <tex>\mathrm{v}_{i}, \mathrm{v}_{i+1}</tex>, где <tex>i \le k</tex> существует ребро, а значит после <tex>n</tex> итераций мы найдем цикл.
