Теорема Хватала — различия между версиями
Vincent (обсуждение | вклад) (Новая страница: «{{Теорема |statement= Пусть '''G''' - связный граф, количество вершин которого не меньше 3. Упорядочи…») |
Vincent (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
Если для <math>\forall k</math> верна импликация <math>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</math> (*), | Если для <math>\forall k</math> верна импликация <math>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</math> (*), | ||
то '''G''' - гамильтонов. | то '''G''' - гамильтонов. | ||
| + | }} | ||
| + | |||
| + | Прежде чем доказать теорему, добавим несколько лемм. | ||
| + | |||
| + | {{Лемма(I) | ||
| + | |statement= | ||
| + | Если <math>\ d_k </math> <= k, то число вершин, степень которых не превосходит k, больше или равно k. | ||
| + | Верно и обратное утверждение. | ||
}} | }} | ||
Версия 03:55, 13 октября 2010
| Теорема: |
Пусть G - связный граф, количество вершин которого не меньше 3. Упорядочим степени вершин G по неубыванию.
Если для верна импликация (*), то G - гамильтонов. |
Прежде чем доказать теорему, добавим несколько лемм.
