210
правок
Изменения
м
Нет описания правки
Предположим, что теорема неверна. Пусть <tex> G </tex> {{---}} максимальный негамильтонов граф с <tex> n </tex> вершинами, удовлетворяющий условиям теоремы.
Легко видеть, что добавление любого ребра в граф, обладающий указанными свойствами, приводит к графу, который также обладает этими свойствами. Таким образом, поскольку добавление к <tex> G </tex> произвольного ребра приводит к гамильтонову ребруграфу, любые две несмежные вершины соединимы простой остовной цепьюпростым гамильтоновым путем.
Покажем сначала, что всякая вершина, степень которой не меньше <tex> (n-1)/2 </tex>, смежна с каждой вершиной со степенью, большей чем <tex> (n-1)/2 </tex>. Не умаляя общности, допустим, что <tex> \deg v_{1} \geqslant (n-1)/2 </tex> и <tex> \deg v_{n} \geqslant n/2 </tex>, но вершины <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны. Тогда существует простая остовная цепь простой гамильтонов путь <tex> v_{1} v_{2} \dotsc v_{n} </tex>, соединяющая соединяющий <tex> v_{1} </tex> и <tex> v_{n} </tex>. Обозначим вершины, смежные с <tex> v_{1} </tex>, через <tex> v_{{i}_{1}}, \dotsc,v_{{i}_{k}} </tex>, где <tex> k = \deg v_{1} </tex> и <tex> 2=i_{1} < i_{2} < \dotsc < i_{k} </tex>. Ясно, что вершина <tex> v_{n} </tex> не может быть смежной ни с одной вершиной из <tex> G </tex> вида <tex> v_{{i}_{j-1}} </tex>, поскольку тогда в <tex> G </tex> был бы гамильтонов цикл <tex> v_{1} v_{2} \dotsc v_{{i}_{j-1}} v_{n} v_{n-1} \dotsc v_{{i}_{j}} v_{1} </tex>.
Далее, так как <tex> k \geqslant (n-1)/2 </tex>, то <tex> n/2 \leqslant \deg v_{n} \leqslant n-1-k < n/2 </tex>, что невозможно. Поэтому <tex> v_{1} </tex> и <tex> v_{n} </tex> должны быть смежны.
Отсюда следует, что если <tex> \deg v \geqslant n/2 </tex> для всех вершин <tex> v </tex>, то <tex> G </tex> {{---}} гамильтонов граф. В силу изложенного выше каждая пара вершин графа <tex> G </tex> смежна, т.е. <tex> G </tex> {{---}} полный граф. Мы пришли к противоречию, поскольку <tex> K_{n} </tex> {{---}} гамильтонов граф для всех <tex> n \geqslant 3 </tex>.
Таким образом, в <tex> G </tex> есть вершина <tex> v </tex> с <tex> \deg v < n/2 </tex>. Обозначим через <tex> m </tex> наибольшую среди степеней всех таких вершин. Выберем такую вершину <tex> v_{1} </tex>, что <tex> \deg v_{1} = m </tex>. По принятому предположению число вершин со степенями, не превосходящими <tex> m </tex>, не больше чем <tex> m < n/2 </tex>, поэтому должно быть более чем <tex> m </tex> вершин со степенями, превосходящими <tex> m </tex>, и, следовательно, не меньшими чем <tex> n/2 </tex>. В результате найдется некоторая вершина, скажем <tex> v_{n} </tex>, степени по крайней мере <tex> n/2 </tex>, не смежная с <tex> v_{1} </tex>. Так как <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны, то существует остовная простая цепь простой гамильтонов путь <tex> v_{1} \dotsc v_{n} </tex>. Как и выше, обозначим через <tex> v_{{i}_{1}}, \dotsc, v_{{i}_{m}} </tex> вершины графа <tex> G </tex>, смежные с <tex> v_{1} </tex>, и заметим, что вершина <tex> v_{n} </tex> не может быть смежной ни с одной из <tex> m </tex> вершин <tex> v_{{i}_{j-1}} </tex> для <tex> 1 \leqslant j \leqslant m </tex>. Но поскольку <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны, а <tex> v_{n} </tex> имеет степень не меньше <tex> n/2 </tex>, то, как было показано в первой части доказательства, <tex> m </tex> должно быть меньше чем <tex> (n-1)/2 </tex>. Так как по предположению число вершин со степенями, не превосходящими <tex> m </tex>, меньше чем <tex> m </tex>, то хотя бы одна из <tex> m </tex> вершин <tex> v_{{i}_{j-1}} </tex>, скажем <tex> v' </tex>, должна иметь степень не меньше <tex> n/2 </tex>. Итак, мы установили, что степени двух несмежных вершин <tex> v_{n} </tex> и <tex> v' </tex> не меньше <tex> n/2 </tex>. Полученное противоречие завершает доказательство теоремы.
}}
