Теорема Хватала

Дан граф [math] G [/math], состоящий из [math]\ n [/math] вершин, [math]\ d_i [/math] — степень [math]\ i [/math]-ой вершины.
Все [math]\ d_i [/math] расположены в порядке неубывания.
[math]\ (*) [/math]: [math]\forall k[/math] верна импликация [math](d_k \le k \lt n/2 \Rightarrow d_{n-k} \ge n-k)[/math].

Лемма (I):

Если [math]\ d_k \le k [/math], то число вершин, степень которых не превосходит [math]\ k [/math], больше или равно [math]\ k [/math]. Верно и обратное утверждение.

Доказательство:

[math]\triangleright[/math]

Так как [math]\ d_1 \le d_2 \le ... \le d_k [/math], то уже есть [math]\ k [/math] вершин, степень которых не превосходит [math]\ k [/math]. Если степени некоторых вершин, следующих за [math]\ k [/math], равны [math]\ d_k [/math], то число вершин, удовлетворяющих требованию, превышает [math]\ k [/math]. Доказательство в обратную сторону: пусть у нас есть [math]\ n [/math] вершин. Из них [math]\ k + p [/math] [math] (p \ge 0) [/math] вершин имеют степень не больше [math]\ k [/math]. Расположим вершины в неубывающем порядке их степеней. [math]\ d_1 \le k, d_2 \le k, ... , d_k \le k, ..., d_{k+p} \le k [/math]. Значит [math]\ d_k \le k [/math].

[math]\triangleleft[/math]

Лемма (II):

Если [math]\ d_{n-k} \ge n-k [/math], то число вершин, степень которых не меньше [math]\ n-k [/math], больше или равно [math]\ k+1 [/math]. Верно и обратное утверждение.

Доказательство:

[math]\triangleright[/math]

Так как [math]\ d_{n-k} \le d_{n-k+1} \le .... \le d_n [/math] и [math]\ d_{n-k} \ge n-k [/math], то мы уже получаем [math]\ d_{n-k}, d_{n-k+1}, ...., d_n = k + 1 [/math] вершин, удовлетворяющих нашему требованию. Если степени некоторых вершин, предшествующих [math]\ n-k [/math], равны [math]\ d_{n-k} [/math], то число вершин, подходящих нашему требованию, превышает [math]\ k+1 [/math]. Доказательство в обратную сторону: пусть у нас есть [math]\ n [/math] вершин. Из них [math]\ k+p [/math] [math] (p \gt 0)[/math] вершин имеют степень не меньше [math]\ n-k [/math]. Расположим вершины в неубывающем порядке их степеней. Получим: [math]\ 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 [/math]. Если [math] p = 1 [/math], то [math] n-k-p+1 = n-k [/math]. Отсюда видно, что [math]\ d_{n-k} \ge n-k [/math].

[math]\triangleleft[/math]

Лемма (III):

Пусть верно следующее: [math] (*) [/math] выполнена для последовательности [math]\ d_1, d_2, ... , d_n [/math]. [math]\ d_1 \le d_1' , ... , d_n \le d_n' [/math]. Тогда [math]\ (*) [/math] выполнена и для [math]\ d_1', ... , d_n' [/math].

Лемма (IV):

Если условие [math]\ (*) [/math] верно для некоторой последовательности степеней, то оно верно и для мажорирующей её последовательности.

Теорема (Хватал):

Пусть [math] G [/math] — связный граф, количество вершин которого не меньше 3. Упорядочим степени вершин [math]\ G [/math] по неубыванию. Если для [math]\forall k[/math] верна [math] (*) [/math]: [math](d_k \le k \lt n/2 \Rightarrow d_{n-k} \ge n-k) [/math], то [math] G [/math] — гамильтонов.

Доказательство:

[math]\triangleright[/math]

Приведем доказательство от противного. Пусть теорема Хватала не верна, то есть существует граф с числом вершин [math]\ n \ge 3 [/math], удовлетворяющий условию [math]\ (*) [/math], но не гамильтонов. Будем добавлять в него рёбра до тех пор, пока не получим максимально возможный негамильтонов граф [math] G [/math] (то есть добавление еще одного ребра сделает граф [math] G [/math] гамильтоновым). Важно то, что добавление рёбер не нарушает условие [math]\ (*) [/math]. Очевидно, что граф [math]\ K_n [/math] гамильтонов для [math]\ k \ge 3 [/math]. Будем считать [math] G [/math] максимальным негамильтоновым остовным подграфом графа [math]\ K_n [/math]. Выберем две несмежные вершины [math] u [/math] и [math] v [/math] графа [math] G [/math] с условием: [math] \deg u + \deg v [/math] — максимально. Будем считать, что [math]\deg u \le \deg v [/math]. Добавив к [math] G [/math] новое ребро [math] e = uv [/math], получим гамильтонов граф [math] G + e[/math]. Рассмотрим гамильтонов цикл графа [math] G + e[/math]: в нём обязательно присутствует ребро [math] e [/math]. Отбрасывая ребро [math] e [/math], получим гамильтонову ([math]u[/math], [math]v[/math])-цепь в графе [math] G [/math]: [math] u = u_1 - u_2 - ... - u_n = v [/math]. Пусть [math]\ S = \{i|e_i = u_1 u_{i+1} \in E(G)\} [/math]. Пусть [math]\ T = \{i|f_i = u_i u_n \in E(G)\} [/math]. [math]\ S \cap T = \varnothing [/math], иначе в графе [math] G [/math] есть гамильтонов цикл: пусть z [math] \in S \cap T [/math]. Тогда получим гамильтонов цикл графа [math] G [/math]: [math]\ u_1 - u_{z+1} - u_{z+2} - ... - u_n - u_z - u_{z-1} - ... - u_1 [/math]. Из определений [math]\ S [/math] и [math]\ T [/math] следует, что [math]\ S \cup T \subseteq \{1, 2, ..., n - 1 \} [/math] , поэтому [math] 2\deg u \le \deg u + \deg v = |S| + |T| = |S \cup T| \lt n [/math], то есть [math]\deg u \lt n/2 [/math]. Так как [math]\ S \cap T = \varnothing [/math], ни одна вершина [math]\ u_j [/math] не смежна с [math]\ v = u_n [/math] (для [math]\ j \in S [/math]). В силу выбора [math] u [/math] и [math] v [/math], получим, что [math]\deg u_j \le \deg u [/math]. Положим, что [math]\ k = \deg u [/math]. Тогда имеется по крайней мере [math]\ |S| = \deg u = k [/math] вершин, степень которых не превосходит k. В силу первой леммы, выполняется: [math]\ d_k \le k \lt n/2 [/math]. Исходя из условия [math]\ (*) [/math], получаем: [math]\ d_{n-k} \ge n-k [/math]. В силу второй леммы, имеется по крайней мере [math]\ k+1 [/math] вершин, степень которых не меньше [math]\ n-k [/math]. Так как [math]\ k = \deg u [/math], то вершина [math]\ u [/math] может быть смежна максимум с [math]\ k [/math] из этих [math]\ k+1 [/math] вершин. Значит, существует вершина [math]\ w [/math], не являющаяся смежной с [math]\ u [/math] и для которой [math]\deg w \ge n-k [/math]. Тогда получим, что [math]\deg u + \deg w \ge k + (n - k) = n \gt \deg u + \deg v [/math], но это противоречит выбору [math]\ u [/math] и [math]\ v [/math].

[math]\triangleleft[/math]

Литература

• Асанов М,, Баранский В., Расин В. — Дискретная математика — Графы, матроиды, алгоритмы