|
Для доказательства теоремы, докажем 3 леммы.
| Лемма (1): |
[math] d_k \leq k \Leftrightarrow |\{ v \in VG | d_v \leq k \}| \geq k. [/math] |
| Доказательство: |
| [math]\triangleright[/math] |
- "[math] \Rightarrow [/math]" Пусть [math] d_1 \leq d_2 \leq \ldots \leq d_k, d_k \leq k, |\{ d_1, d_2, \ldots, d_k \}| = k [/math].
[math] \{ d_1, d_2, \ldots, d_k \} \subset \{ v \in VG | d_v \leq k \} \Rightarrow |\{ v \in VG | d_v \leq k \}| \geq k [/math], q.e.d.
- "[math] \Leftarrow [/math]" Пусть [math] |\{ v \in VG | d_v \leq k \}| = k + p, p \geq 0 [/math]. Расположим вершины в неубывающем порядке их степеней.
[math] d_1 \leq d_2 \leq \ldots \leq d_k \leq \ldots \leq d_{k + p} \leq k \Rightarrow d_k \leq k [/math], q.e.d. | | [math]\triangleleft[/math] |
| Лемма (2): |
[math]\ d_{n - k} \geq n - k \Leftrightarrow |\{ v \in VG | d_v \geq n - k \}| \geq k + 1. [/math] |
| Доказательство: |
| [math]\triangleright[/math] |
- "[math] \Rightarrow [/math]" Пусть [math] d_{n - k} \geq n - k, d_{n - k} \leq d_{n - k + 1} \leq \ldots \leq d_n, |\{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \}| = k + 1 [/math]
[math] \{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \} \subset \{ v \in VG | d_v \geq n - k \} \Rightarrow \{ v \in VG | d_v \geq n - k \} \geq k + 1 [/math], q.e.d.
- "[math] \Leftarrow [/math]" Пусть [math] |\{ v \in VG | d_v \geq n - k \}| = k + 1 + p, p \geq 0 [/math]. Расположим вершины в неубывающем порядке их степеней.
[math] d_n \geq d_{n - 1} \ldots \geq d_{n - k} \geq \ldots \geq d_{n - k - p} \geq n - k \Rightarrow d_{n - k} \geq n - k [/math], q.e.d. | | [math]\triangleleft[/math] |
| Лемма (3): |
Если импликация [math] (*) [/math] верна для некоторой последовательности степеней [math] d [/math], то она верна и для неубывающей последовательности [math] d' [/math], мажорирующей [math] d [/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].
|
