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

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

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

Прежде чем доказать теорему, добавим несколько лемм.

Лемма (I):

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

Лемма (II):

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

Лемма (III):

Пусть (*) выполнена для последовательности [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]