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

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