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

Теорема:

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

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