748
правок
Изменения
Нет описания правки
* Рассмотрим элементы с номерами <tex> s = \overline{1, i - 1} </tex>. Они не изменились, следовательно мажорируются собой.
* Рассмотрим элементы с номерами <tex> s = \overline{i, j - 1} </tex>. <tex> s </tex>-й элемент полученной последовательности равен <tex> s + 1 </tex>-му элементу исходной. <tex> d_s \leq leqslant d_{s + 1} \Rightarrow d_s \leqslant d'_s = d_{s + 1} </tex>.
* Расмотрим <tex>j</tex>-ый элемент. Имеем <tex>d'_j \ge d'_{j-1} = d_{j} </tex>.
* Рассмотрим элементы с номерами <tex> s = \overline{j + 1, n} </tex>. Они не изменились, следовательно мажорируются собой.
Пусть:
* <tex> G </tex> — [[Отношение_связности,_компоненты_связности#.D0.A1.D0.BB.D1.83.D1.87.D0.B0.D0.B9_.D0.BD.D0.B5.D0.BE.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D0.BE.D0.B3.D0.BE_.D0.B3.D1.80.D0.B0.D1.84.D0.B0|связный граф]],
* <tex> n = |VG| \geq geqslant 3 </tex> — количество вершин,
* <tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n </tex> — его последовательность степеней.
Тогда если <tex> \forall k \in \mathbb N </tex> верна импликация: <br>
<center><tex> d_k \leqslant k < n/2 \rightarrow d_{n - k} \geq geqslant n - k, (*) </tex></center>
то граф <tex> G </tex> [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов]].
|proof=
1
|statement=
<tex> d_k \leqslant k \Leftrightarrow |\{ v \in VG | d_v \leqslant k \}| \geq geqslant k. </tex>
|proof=
"<tex> \Rightarrow </tex>" Пусть:
* <tex> d_k \leqslant k </tex>,
* <tex> |\{ d_1, d_2, \ldots, d_k \}| = k </tex>.
<tex> \{ d_1, d_2, \ldots, d_k \} \subseteq \{ v \in VG | d_v \leqslant k \} \Rightarrow |\{ v \in VG | d_v \leqslant k \}| \geq geqslant k </tex>, q.e.d.
"<tex> \Leftarrow </tex>" Пусть:
* <tex> |\{ v \in VG | d_v \leqslant k \}| = k + p </tex>,
* <tex> p \geq geqslant 0 </tex>.
Расположим вершины в неубывающем порядке их степеней. <br>
<tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_k \leqslant \ldots \leqslant d_{k + p} \leqslant k \Rightarrow d_k \leqslant k </tex>, q.e.d.
2
|statement=
<tex>\ d_{n - k} \geq geqslant n - k \Leftrightarrow |\{ v \in VG | d_v \geq geqslant n - k \}| \geq geqslant k + 1. </tex>
|proof=
"<tex> \Rightarrow </tex>" Пусть:
* <tex> d_{n - k} \geq geqslant n - k </tex>,
* <tex> d_{n - k} \leqslant d_{n - k + 1} \leqslant \ldots \leqslant d_n </tex>,
* <tex> |\{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \}| = k + 1 </tex>.
<tex> \{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \} \subseteq \{ v \in VG | d_v \geq geqslant n - k \} \Rightarrow \{ v \in VG | d_v \geq geqslant n - k \} \geq geqslant k + 1 </tex>, q.e.d.
"<tex> \Leftarrow </tex>" Пусть:
* <tex> |\{ v \in VG | d_v \geq geqslant n - k \}| = k + 1 + p, (p \geq geqslant 0)</tex>,
Расположим вершины в неубывающем порядке их степеней.
<tex> d_n \geq geqslant d_{n - 1} \ldots \geq geqslant d_{n - k} \geq geqslant \ldots \geq geqslant d_{n - k - p} \geq geqslant n - k \Rightarrow d_{n - k} \geq geqslant n - k </tex>, q.e.d.
}}
|proof=
# Пусть <tex> d'_k > k </tex>. Тогда первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента. Значит, в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.
# Пусть <tex> d'_k \leqslant k, \mbox{ } d'_{n - k} \geq geqslant d_{n - k} \geq geqslant n - k </tex>. Тогда оба аргумента импликации всегда истинны. Значит, и в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.
Значит, импликация <tex> (*) </tex> выполняется и для последовательности <tex> d' </tex>, q.e.d.
}}
Приведем доказательство от противного.
Пусть существует граф с числом вершин <tex> n \geq geqslant 3 </tex>, удовлетворяющий <tex> (*) </tex>, но негамильтонов.
Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым).
По лемме о добавлении ребра и лемме №3 импликация <tex> (*) </tex> остается верной для графа <tex> G </tex>.
Очевидно, что граф <tex>\ K_n </tex> гамильтонов при <tex> k \geq geqslant 3 </tex>.
Будем считать <tex> G </tex> максимальным негамильтоновым остовным подграфом графа <tex> K_n </tex>.
Так как <tex> S \cap T = \emptyset </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 \leqslant \deg u </tex>. Пусть <tex> k = \deg u = |S| </tex>. Значит, <tex> \exists k </tex> вершин, степень которых не превосходит <tex> k </tex>.
По лемме №1: <tex> d_k \leqslant k < n/2 </tex>. В силу импликации <tex> (*) </tex>: <tex> d_{n - k} \geq geqslant n - k </tex>.
По лемме №2, <tex> \exists k + 1 </tex> вершин, степень которых не меньше <tex> n - k </tex>.
Так как <tex> k = \deg u </tex>, то вершина <tex> u </tex> может быть смежна максимум с <tex> k </tex> из этих <tex> k+1 </tex> вершин. Значит, существует вершина <tex> w </tex>, не являющаяся смежной с <tex> u </tex> и для которой <tex> \deg w \geq geqslant n - k </tex>. Тогда получим, что <tex> \deg u + \deg w \geq geqslant k + (n - k) = n > \deg u + \deg v </tex>, что противоречит выбору <tex> u </tex> и <tex> v </tex>.
Значит, предположение неверно, q.e.d.
