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

Теорема:

Пусть 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 [/math] <= k, то число вершин, степень которых не превосходит k, больше или равно k. Верно и обратное утверждение.

Лемма (II):

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