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