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

Материал из Викиконспекты
Перейти к: навигация, поиск
Теорема:
Пусть 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. Верно и обратное утверждение.