Изменения

Перейти к: навигация, поиск

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

13 байт добавлено, 08:13, 3 ноября 2010
Нет описания правки
|statement=
Пусть <tex> G </tex> - [[Отношение связности, компоненты связности|связный граф]], количество вершин которого не меньше 3. Упорядочим степени вершин <tex>\ G </tex> по неубыванию.
Если для <tex>\forall k</tex> верна импликация <tex>(d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k) </tex> <tex> (*) </tex>,то <tex> G </tex> - [[Гамильтоновы графы|гамильтонов]].
|proof=
Приведем доказательство от противного.
Анонимный участник

Навигация