Изменения

Для вершин <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> } Имеем: <math>\left\vert S \right\vert + \left\vert T \right\vert = deg\ u + deg \ v \ge n </math>, но <math>\left\vert S + T \right\vert < n.</math> И тогда: <math>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</math> т.е. <math>\exists i| ut_{i+1}\in EG</math> и <math> t_iv \in EG.</math>