|
Для доказательства теоремы, докажем 3 леммы.
| Лемма (1): |
[math] d_k \leqslant k \Leftrightarrow |\{ v \in VG \mid d_v \leqslant k \}| \geqslant k. [/math] |
| Доказательство: |
| [math]\triangleright[/math] | |
[math] \Rightarrow [/math] Пусть:
- [math] d_1 \leqslant d_2 \leqslant \ldots \leqslant d_k [/math],
- [math] d_k \leqslant k [/math],
- [math] |\{ d_1, d_2, \ldots, d_k \}| = k [/math].
[math] \{ d_1, d_2, \ldots, d_k \} \subseteq \{ v \in VG \mid d_v \leqslant k \} \Rightarrow |\{ v \in VG \mid d_v \leqslant k \}| \geqslant k [/math].
[math] \Leftarrow [/math] Из условия:
- [math] |\{ v \in VG \mid d_v \leqslant k \}| = k + p [/math],
- [math] p \geqslant 0 [/math].
Расположим вершины в неубывающем порядке их степеней.
[math] d_1 \leqslant d_2 \leqslant \ldots \leqslant d_k \leqslant \ldots \leqslant d_{k + p} \leqslant k \Rightarrow d_k \leqslant k [/math]. | | [math]\triangleleft[/math] |
| Лемма (2): |
[math]\ d_{n - k} \geqslant n - k \Leftrightarrow |\{ v \in VG \mid d_v \geqslant n - k \}| \geqslant k + 1. [/math] |
| Доказательство: |
| [math]\triangleright[/math] | |
[math] \Rightarrow [/math] Пусть:
- [math] d_{n - k} \geqslant n - k [/math],
- [math] d_{n - k} \leqslant d_{n - k + 1} \leqslant \ldots \leqslant d_n [/math],
- [math] |\{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \}| = k + 1 [/math].
[math] \{ d_{n - k}, d_{n - k + 1}, \ldots , 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 [/math].
[math] \Leftarrow [/math]:
- [math] |\{ v \in VG \mid d_v \geqslant n - k \}| = k + 1 + p, (p \geqslant 0)[/math],
Расположим вершины в неубывающем порядке их степеней.
[math] 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 [/math]. | | [math]\triangleleft[/math] |
| Лемма (3): |
Если импликация [math] (*) [/math] верна для некоторой последовательности степеней [math] d [/math], то она верна и для неубывающей последовательности [math] d' [/math], мажорирующей [math] d [/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
- Если [math] d'_k \gt k [/math], то первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента. Значит, в этом случае импликация [math] (*) [/math] верна для последовательности [math] d' [/math].
- Если [math] d'_k \leqslant k, \mbox{ } d'_{n - k} \geqslant d_{n - k} \geqslant n - k [/math], то оба аргумента импликации всегда истинны. Значит, и в этом случае импликация [math] (*) [/math] верна для последовательности [math] d' [/math].
Значит, импликация [math] (*) [/math] выполняется и для последовательности [math] d' [/math]. | | [math]\triangleleft[/math] |
Приведем доказательство от противного.
Пусть существует граф с числом вершин [math] n \geqslant 3 [/math], удовлетворяющий [math] (*) [/math], но негамильтонов.
Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф [math] G [/math] (то есть добавление еще одного ребра сделает граф [math] G [/math] гамильтоновым).
По лемме о добавлении ребра и лемме №3 импликация [math] (*) [/math] остается верной для графа [math] G [/math].
Очевидно, что граф [math]\ K_n [/math] гамильтонов при [math] k \geqslant 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 \leqslant \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, v) [/math]-цепь в графе [math] G [/math]: [math] u = u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_n = v [/math].
Пусть [math] S = \{ i \mid e_i = u_1 u_{i + 1} \in EG\}, T = \{ i \mid f_i = u_i u_n \in EG\} [/math].
 Множество [math] S [/math] обозначено красным цветом, множество [math] T [/math] обозначено синим цветом
| Утверждение: |
[math] S \cap T = \emptyset [/math]. |
| [math]\triangleright[/math] | |
Предположим, что [math] j \in S \cap T [/math]. Тогда получим гамильтонов цикл графа [math] G [/math]: [math] u_1 \xrightarrow{e_j} u_{j + 1} \rightarrow \ldots \rightarrow u_n \xrightarrow{f_j} u_j \rightarrow u_{j - 1} \rightarrow \ldots \rightarrow u_1 [/math], что противоречит условию, что граф негамильтонов.
Значит, [math] S \cap T [/math]. | | [math]\triangleleft[/math] |
Из определений [math] S [/math] и [math] T [/math] следует, что [math] S \cup T \subseteq \{1, 2, ..., n - 1 \} \Rightarrow 2 \deg u \leqslant \deg u + \deg v = |S| + |T| = |S \cup T| \lt n [/math]. Значит, [math] \deg u \lt n/2 [/math].
Так как [math] S \cap T = \emptyset [/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 \leqslant \deg u [/math]. Пусть [math] k = \deg u = |S| [/math]. Значит, [math] \exists k [/math] вершин, степень которых не превосходит [math] k [/math].
По лемме №1: [math] d_k \leqslant k \lt n/2 [/math]. В силу импликации [math] (*) [/math]: [math] d_{n - k} \geqslant n - k [/math].
По лемме №2, [math] \exists 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 \geqslant n - k [/math]. Тогда получим, что [math] \deg u + \deg w \geqslant k + (n - k) = n \gt \deg u + \deg v [/math], что противоречит выбору [math] u [/math] и [math] v [/math].
Значит, предположение неверно. |
