271
правка
Изменения
Нет описания правки
Дан [[Основные определения теории графов|граф]] <tex> G </tex>, состоящий из <tex>\ n </tex> [[Основные определения теории графов|вершин]], <tex>\ d_i </tex> - — [[Основные определения теории графов|степень]] <tex>\ i </tex> - ой вершины. <br>
Все <tex>\ d_i </tex> расположены в порядке неубывания. <br>
<tex>\ (*): </tex> <tex>\forall k</tex> верна импликация <tex>(d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k)</tex> <br>
Верно и обратное утверждение.
|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>
Доказательство в обратную сторону: <br>
Пусть у нас есть <tex>\ n </tex> вершин. Из них <tex>\ k + p (p \ge 0) </tex> вершин имеют степень не больше <tex>\ k </tex>.
Верно и обратное утверждение.
|proof=
Так как <tex>\ d_{n-k} \le d_{n-k+1} \le .... \le d_n </tex> и <tex>\ d_{n-k} \ge n-k </tex>, то мы уже получаем <tex>\ d_{n-k}, d_{n-k+1}, ...., d_n = k + 1 </tex> вершинувершин, удовлетворяющую удовлетворяющих нашему требованию. Если степени некоторых вершин, предшествующих <tex>\ n-k </tex> , равны <tex>\ d_{n-k} </tex>, то число вершин, подходящих нашему требованию, превышает <tex>\ k+1 </tex> <br>
Доказательство в обратную сторону: <br>
Пусть у нас есть <tex>\ n </tex> вершин. Из них <tex>\ k+p (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>.
III
|statement=
# Пусть <tex>\ (*) </tex> выполнена для последовательности <tex>\ d_1, d_2, ... , d_n </tex>. # Пусть <tex>\ d_1 \le d_1' , ... , d_n \le d_n' </tex>.
Тогда <tex>\ (*) </tex> выполнена и для <tex>\ d_1', ... , d_n' </tex>
}}
<br>
{{Лемма
|about=
IV
|statement=
}}
<br>
{{Теорема
|about=
Хватал
|statement=
Пусть <tex> G </tex> - — [[Отношение связности, компоненты связности|связный граф]], количество вершин которого не меньше 3. Упорядочим степени вершин <tex>\ G </tex> по неубыванию.Если для <tex>\forall k</tex> верна импликация <tex>(d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k) </tex> <tex> (*) </tex>, то <tex> G </tex> - — [[Гамильтоновы графы|гамильтонов]].
|proof=
Приведем доказательство от противного.
Очевидно, что граф <tex>\ K_n </tex> гамильтонов для <tex>\ k \ge 3 </tex>.
Будем считать <tex> G </tex> максимальным негамильтоновым остовным подграфом графа <tex>\ K_n </tex>.
Выберем две несмежные вершины <tex> u </tex> и <tex> v </tex> графа <tex> G </tex> с условием : <tex> \deg u + \deg v </tex> - — максимально.
Будем считать, <tex>\deg u \le \deg v </tex>.
Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e</tex>.
<tex>\ S \cap T = \varnothing </tex>, иначе в графе <tex> G </tex> есть гамильтонов цикл. Пусть j <tex> \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex> : <tex>\ u_1 - u_{j+1} - u_{j+2} - ... - u_n - u_j - u_{j-1} - ... - u_1 </tex>.
Из определений <tex>\ S </tex> и <tex>\ T </tex> следует, что <tex>\ S \cup T \subseteq \{1, 2, ..., n - 1 \} </tex> , поэтому <tex> 2\deg u \le \deg u + \deg v = |S| + |T| = |S \cup T| < n </tex>, то есть <tex>\deg u < n/2 </tex>. <br>
Так как <tex>\ S \cap T = \varnothing </tex>, ни одна вершина <tex>\ u_j </tex> не смежна с <tex>\ v = u_n </tex> (для <tex>\ j \in S </tex>). Отсюда в силу выбора <tex> u </tex> и <tex> v </tex> имеем <tex>\deg u_j \le \deg u </tex>. Положим , что <tex>\ k = \deg u </tex>.
Тогда имеется по крайней мере <tex>\ |S| = \deg u = k </tex> вершин, степень которых не превосходит k. <br>
В силу леммы(I) выполняется : <tex>\ d_k \le k < n/2 </tex>. <br>
По условию <tex>\ (*) </tex> получаем : <tex>\ d_{n-k} \ge n-k </tex>. <br>
В силу леммы(II) имеется по крайней мере <tex>\ k+1 </tex> вершин, степень которых не меньше <tex>\ n-k </tex>. <br>
Так как <tex>\ k = \deg u </tex>, то вершина <tex>\ u </tex> может быть смежнане больше, самое большее, чем с <tex>\ k </tex> из этих <tex>\ k+1 </tex> вершин. Значит существует вершина <tex>\ w </tex>, несмежная не являющаяся смежной с <tex>\ u </tex>, и для которой <tex>\deg w \ge n-k </tex>. Но тогда получим <tex>\deg u + \deg w \ge k + (n - k) = n > \deg u + \deg v </tex>, что противоречит выбору <tex>\ u </tex> и <tex>\ v </tex>. <br>
}}
