Изменения

Все {{Определение|definition=Пусть [[Основные_определения_теории_графов#.D0.9D.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.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|неориентированный граф]] <tex> G </tex> имеет <tex> n </tex> вершин: <mathtex>v_1, v_2, \ d_i ldots, v_n </mathtex> расположены в порядке неубывания. Пусть <br><mathtex>d_i = \deg v_i \ mbox{ } (*i = \overline{1, n}): </mathtex> и вершины графа упорядочены таким образом, что <mathtex>d_1 \leqslant d_2 \leqslant \forall kldots \leqslant d_n </mathtex> верна импликация . Последовательность <mathtex>(d_k d_1, d_2, \le k ldots, d_n < n/2 \Rightarrow d_{n-k} \ge n-k)tex> называют '''последовательностью степеней''' графа </mathtex> G <br/tex>.}} 

Если Пусть неориентированный граф <mathtex>\ d_k \le k G' </mathtex>, то число вершин, степень которых не превосходит получен из неориентированного графа <mathtex>\ k G </mathtex>, больше или равно добавлением одного нового ребра <mathtex>\ k e </mathtex>. Верно и обратное утверждениеТогда последовательность степеней графа <tex> G </tex> мажорируется последовательностью степеней графа <tex> G' </tex>.

Т.к. ''Замечание'': Если в неубывающей последовательности <mathtex>\ d_1 \le , d_2 , \le ... \le d_k ldots, d_n </mathtex>, то уже есть увеличить на единицу число <mathtex>\ k d_i </mathtex> вершин, степень которых не превосходит а затем привести последовательность к неубывающему виду, переставив число <mathtex>\ k d_i + 1 </mathtex>. Если степени некоторых вершин, следующих за на положенное место <mathtex>\ k j </mathtex> равны , то исходная последовательность будет мажорироваться полученной. Если <mathtex>\ d_k j = i</mathtex>, то число вершинутверждение леммы, удовлетворяющих требованиюочевидно, превышает выполняется. Пусть <mathtex>j \ k neq i</mathtex>. [[Файл: Hvatal_1.png|270px|thumb|center|Исходная последовательность степеней <brtex>d </tex>]]Доказательство в обратную сторону: * Рассмотрим элементы с номерами <tex> s = \overline{1, i - 1} <br/tex>. Они не изменились, следовательно мажорируются собой.Пусть у нас есть * Рассмотрим элементы с номерами <mathtex>s = \ n overline{i, j - 1} </tex>. <tex> s </tex>-й элемент полученной последовательности равен <tex> s + 1 </mathtex> вершин-му элементу исходной. Из них <mathtex>d_s \ k leqslant d_{s + p (p 1} \Rightarrow d_s \ge 0) leqslant d'_s = d_{s + 1} </tex>.* Расмотрим <tex>j</mathtex> вершин имеют степень не больше -ый элемент. Имеем <mathtex>d'_j \ k ge d'_{j-1} = d_{j} </mathtex>.Расположим вершины в неубывающем порядке их степеней. * Рассмотрим элементы с номерами <mathtex>s = \ d_1 \le koverline{j + 1, d_2 \le kn} </tex>. Они не изменились, следовательно мажорируются собой.[[Файл: Hvatal_2.. png|290px|thumb|center|Новая последовательность степеней <tex> d' </tex>]]При добавлении в граф ребра <tex> e = uv, d_k \le k, ..., d_mbox{k+p} (u \le k neq v) </mathtex>. Значит , степени вершин <tex> u </tex> и <mathtex>\ d_k \le k v </mathtex>увеличатся на единицу. Для доказательства леммы, дважды воспользуемся замечанием.Значит, последовательность степеней полученного графа мажорирует последовательность степеней исходного.

Если <mathtex>d_k \leqslant k \Leftrightarrow |\ d_{n-k} v \in VG \mid d_v \ge n-leqslant k </math>, то число вершин, степень которых не меньше <math>\ n-k </math>, больше или равно <math>}| \ geqslant k+1 . </mathtex>.Верно и обратное утверждение.

Т.к. <mathtex> \Rightarrow </tex> Пусть:* <tex>d_1 \ d_{n-k} leqslant d_2 \le d_{n-k+1} leqslant \le .... ldots \le d_n leqslant d_k </mathtex> и ,* <mathtex>d_k \ d_{n-k} \ge n-leqslant k </mathtex>, то мы уже получаем * <mathtex>|\ d_{n-k}d_1, d_{n-k+1}d_2, ....\ldots, d_n d_k \}| = k + 1 </mathtex> вершину, удовлетворяющую нашему требованию. Если степени некоторых вершин, предшествующих <mathtex>\ n-{ d_1, d_2, \ldots, d_k \} \subseteq \{ v \in VG \mid d_v \leqslant k </math> равны <math>\ d_} \Rightarrow |\{n-v \in VG \mid d_v \leqslant k\} </math>, то число вершин, подходящих нашему требованию, превышает <math>| \ geqslant k+1 </math> <brtex>.Доказательство в обратную сторону: <br>Пусть у нас есть <mathtex>\ n Leftarrow </mathtex> вершин. Из них условия:* <mathtex>|\{ v \in VG \mid d_v \leqslant k \ }| = k+p (p > 0)</mathtex> вершин имеют степень не меньше ,* <mathtex>p \ n-k geqslant 0 </mathtex>. Расположим вершины в неубывающем порядке их степеней. Получим : <mathbr><tex>d_1 \leqslant d_2 \ d_n leqslant \ge n-k, d_{n-1} ldots \leqslant d_k \leqslant \ge n-k, ..., d_{n-k} ldots \ge n-k, ... , leqslant d_{n-k-+ p+1} \ge n-leqslant k </math>. Если p = 1, то n-k-p+1 = n-k. Отсюда видно, что <math>\ d_{n-k} Rightarrow d_k \ge n-leqslant k </mathtex>.

<tex>\ d_{n - k} \geqslant n - k \Leftrightarrow |\{ v \in VG \mid d_v \geqslant n - k \}| \geqslant k + 1. </tex>|proof=<tex> \Rightarrow </tex> Пусть :* <mathtex>d_{n - k} \ (geqslant n - k </tex>,*) <tex> d_{n - k} \leqslant d_{n - k + 1} \leqslant \ldots \leqslant d_n </mathtex> выполнена для последовательности , * <mathtex>|\ d_1{ d_{n - k}, d_2d_{n - k + 1}, ... \ldots , d_n \}| = k + 1 </mathtex>. Пусть <mathtex>\ d_1 { d_{n - k}, d_{n - k + 1}, \le d_1' , ... ldots , d_n \le d_n' } \subseteq \{ v \in VG \mid d_v \geqslant n - k \} \Rightarrow \{ v \in VG \mid d_v \geqslant n - k \} \geqslant k + 1 </mathtex>.Тогда <mathtex>\ (*) Leftarrow </mathtex> выполнена и для :* <mathtex>|\{ v \ d_1'in VG \mid d_v \geqslant n - k \}| = k + 1 + p, (p \geqslant 0)</tex>,Расположим вершины в неубывающем порядке их степеней... , <tex> d_n' \geqslant d_{n - 1} \ldots \geqslant d_{n - k} \geqslant \ldots \geqslant d_{n - k - p} \geqslant n - k \Rightarrow d_{n - k} \geqslant n - k </mathtex>.

Если условие импликация <mathtex>\ (*) </mathtex> верно верна для некоторой последовательности степеней<tex> d </tex>, то оно верно она верна и для неубывающей последовательности <tex> d' </tex>, мажорирующей ее <tex> d </tex>.|proof=# Если <tex> d'_k > k </tex>, то первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента. Значит, в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.# Если <tex> d'_k \leqslant k, \mbox{ } d'_{n - k} \geqslant d_{n - k} \geqslant n - k </tex>, то оба аргумента импликации всегда истинны. Значит, и в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.Значит, импликация <tex> (*) </tex> выполняется и для последовательности<tex> d' </tex>.

Приведем доказательство от противного. Пусть существует граф с числом вершин <tex> n \geqslant 3 </tex>, удовлетворяющий <tex> (*) </tex>, но негамильтонов.Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым). По лемме о добавлении ребра и лемме №3 импликация <tex> (*) </tex> остается верной для графа <tex> G </tex>.Очевидно, что граф <tex>\ K_n </tex> гамильтонов при <tex> k \geqslant 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 \leqslant \deg v </tex>.Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e </tex>.Рассмотрим гамильтонов цикл графа <tex> G + e </tex>: в нём обязательно присутствует ребро <tex> e </tex>.Отбрасывая ребро <tex> e </tex>, получим гамильтонову <tex> (u, v) </tex>-цепь в графе <tex> G </tex>: <tex> u = u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_n = v </tex>. Пусть <tex> S = \{i \mid e_i = u_1 u_{Теоремаi + 1} \in EG\}, T = \{ i \mid f_i = u_i u_n \in EG\} </tex>.[[Файл: Hvatal_3.png|330px|thumb|center|about=Множество <tex> S </tex> обозначено красным цветом, множество <tex> T </tex> обозначено синим цветом]] Хватала{{Утверждение

Пусть '''G''' - связный граф, количество вершин которого не меньше 3. Упорядочим степени вершин '''G''' по неубыванию.Если для <mathtex>S \forall k</math> верна импликация <math>(d_k \le k < n/2 \Rightarrow d_{n-k} cap T = \ge n-k) (*) emptyset </mathtex>,то '''G''' - гамильтонов.

Приведем доказательство от противного.Пусть теорема Хватала не верна, есть граф , где <math>\ n \ge 3 </math>, удовлетворяющий условию <math>\ (*) </math>, но не гамильтонов.Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф '''G'''(т.е. добавление еще одного ребра сделает граф '''G''' гамильтоновым). Добавление ребер не противоречит условию <math>\ (*) </math>.ОчевидноПредположим, что граф <mathtex>j \ K_n </math> гамильтонов для <math>in S \ k \ge 3 cap T </mathtex>.Будем считать '''G''' максимальным негамильтоновым остовным подграфом графа <math>\ K_n </math>.Выберем две несмежные вершины U и V графа '''G''' с условием : <math>\ degU + degV </math> - максимально.Будем считать, <math>\ degU \le degV </math>.Добавив к '''G''' новое ребро e = UV, Тогда получим гамильтонов граф '''G''' + UV.Рассмотрим гамильтонов цикл графа '''G''' + UV : в нем обязательно присутствует ребро UV. <brtex>Отбрасывая ребро UV, получим гамильтонову (U, V)-цепь в графе '''G''' : <math>\ U = U_1 - U_2 - ... - U_n = V </mathtex>. <br>Пусть : <mathtex>u_1 \ S = \xrightarrow{i|e_i = U_1 U_e_j} u_{ij +1} \in E(G)rightarrow \} </math> <br>Пусть <math>ldots \ T = rightarrow u_n \xrightarrow{i|f_i = U_i U_n \in E(G)f_j} u_j \rightarrow u_{j - 1} </math> <br> <math>\ S rightarrow \cap T = ldots \empty rightarrow u_1 </mathtex>, иначе в графе '''G''' есть гамильтонов циклчто противоречит условию, что граф негамильтонов.[[Файл: Hvatal_4. Пусть j png|270px|thumb|center|]]Значит, <mathtex> \in S \cap T </mathtex>. Тогда получим гамильтонов цикл графа '''G''' : <math>\ U_1 - U_{j+1} - U_{j+2} - ... - U_n - U_j - U_{j-1} - ... - U_1 </math> <br> Из определений <mathtex>\ S </mathtex> и <mathtex>\ T </mathtex> следует, что <mathtex>\ S \cup T \sube subseteq \{1, 2, ..., n - 1 \} </math> , поэтому <math>\ 2degU Rightarrow 2 \deg u \leqslant \le degU deg u + degV \deg v = |S| + |T| = |S \cup T| < n </mathtex>. Значит, т.е. <mathtex>\ degU deg u < n/2 </math> <brtex>. Т.к. Так как <mathtex>\ S \cap T = \empty emptyset </mathtex>, ни одна вершина <mathtex>\ U_j u_j </mathtex> не смежна с <mathtex>\ V v = U_n u_n </mathtex> (для <mathtex>\ j \in S </mathtex>). Отсюда в В силу выбора <mathtex>\ U u </mathtex> и <mathtex>\ V v </mathtex> имеем , получим, что <mathtex>\ degU_j deg u_j \le degU leqslant \deg u </mathtex>. Положим Пусть <mathtex>k = \ k deg u = degU |S| </mathtex>.Тогда имеется по крайней мере Значит, <mathtex>\ |S| = degU = exists k </mathtex> вершин, степень которых не превосходит <tex> k. <br/tex>. В силу леммы(I) выполняется По лемме №1: <mathtex>\ d_k \le leqslant k < n/2 </mathtex> . В силу импликации <br>По условию <mathtex>\ (*) </mathtex> получаем : <mathtex>\ d_{n-k} \ge geqslant n-k </math> <brtex>. В силу леммы(II) имеется по крайней мере По лемме №2, <mathtex>\ exists k+1 </mathtex> вершин, степень которых не меньше <mathtex>\ n-k </math> <brtex>. Так как <mathtex>\ k = degU \deg u </mathtex>, то вершина <mathtex>\ U u </mathtex> может быть смежна, самое большее, максимум с <mathtex>\ k </mathtex> из этих <mathtex>\ k+1 </mathtex> вершин. Значит , существует вершина <mathtex>\ W w </mathtex>, несмежная не являющаяся смежной с <mathtex>\ U u </mathtex>, и для которой <mathtex>\ degW deg w \ge geqslant n-k </mathtex>. Но тогда Тогда получим , что <mathtex>\ degU deg u + degW \ge deg w \geqslant k + (n - k) = n > degU \deg u + degV \deg v </mathtex>, что противоречит выбору <mathtex>\ U u </mathtex> и <mathtex>\ V v </mathtex>. <br> Значит, предположение неверно.