54
правки
Изменения
м
Нет описания правки
Для вершин <math>\ u,v</math> выполнено <math>deg\ u + deg \ v \ge n.</math>
По принципу Дирихле, всегда найдутся две смежные вершины <math>\ t_1,t_2</math> на пути <math>\ (u,v)</math> ,т.е. <math>\ u..t_1t_2..v</math> , такие, что существует ребро <math>\ ut_2</math> и ребро <math>\ t_1v.</math>
Действительно, пусть <math>\ S = </math> { <math> i| e_i=ut_{i+1} \in EG</math> } и <math>\ T = </math> { <math> i| f_i=t_iv \in EG</math> }
