272
правки
Изменения
Нет описания правки
|about=
|statement=
Пусть <tex> G </tex> — [[Отношение связности, компоненты связности|связный граф]], <tex> n = |VG| \geq 3 </tex> — количество вершин, <tex> d_1 \leq d_2 \leq \ldots \leq d_n </tex> — последовательность степеней. <br>Если <tex>\ forall k \in \mathbb N </tex> верна импликация: <br><center><tex> d_k \le leq k < n/2 \rightarrow d_{n-k} \geq n-k , (*)</tex>, </center><br>то число вершин, степень которых не превосходит граф <tex>\ k G </tex>[[Гамильтоновы графы|гамильтонов]].|proof=Для доказательства теоремы, больше или равно докажем 3 леммы.# {{Лемма|statement=<tex>\ d_k \leq k \Leftrightarrow |\{ v \in |VG| : d_v \leq k \}| \geq k </tex>. Верно и обратное утверждение.
|proof=
Так как <tex>\ d_1 \le d_2 \le ... \le d_k </tex>, то уже есть <tex>\ k </tex> вершин, степень которых не превосходит <tex>\ k </tex>. Если степени некоторых вершин, следующих за <tex>\ k </tex>, равны <tex>\ d_k </tex>, то число вершин, удовлетворяющих требованию, превышает <tex>\ k </tex>. <br>
}}
# {{Лемма|about=II
|statement=
Если <tex>\ d_{n-k} \ge n-k </tex>, то число вершин, степень которых не меньше <tex>\ n-k </tex>, больше или равно <tex>\ k+1 </tex>.
'''Доказательство в обратную сторону:''' <br>
пусть у нас есть <tex>\ n </tex> вершин. Из них <tex>\ k+p </tex> <tex> (p > 0)</tex> имеют степень не меньше <tex>\ n-k </tex>. Расположим вершины в неубывающем порядке их степеней. Получим: <tex>\ d_n \ge n-k, d_{n-1} \ge n-k, ..., d_{n-k} \ge n-k, ... , d_{n-k-p+1} \ge n-k </tex>. Если <tex> p = 1 </tex>, то <tex> n-k-p+1 = n-k </tex>. Отсюда видно, что <tex>\ d_{n-k} \ge n-k </tex>.
}}
}}
