210
правок
Изменения
м
→Достаточные условия гамильтоновости графа
|statement=
Если <tex>n \ge 3</tex> и <tex>deg\ u + deg\ v \ge n</tex> для любых двух различных несмежных вершин <tex>u</tex> и <tex>v</tex> неориентированного графа <tex>G</tex>, то <tex>G</tex> - гамильтонов граф.
}}
===[[Теорема Поша|Теорема Поша]]===
{{Теорема
|about = Поша
|statement = Пусть граф <tex> G </tex> имеет <tex>n \geqslant 3</tex> вершин и выполнены следующие два условия:
*для всякого <tex>k,\, 1 \leqslant k < (n-1)/2</tex>, число вершин со степенями, не превосходящими <tex>k</tex>, меньше чем <tex>k</tex>;
*для нечетного <tex>n</tex> число вершин степени <tex>(n-1)/2</tex> не превосходит <tex>(n-1)/2</tex>,
тогда <tex> G </tex> {{---}} гамильтонов граф.
}}
===[[Теорема_Редеи-Камиона|Теорема Редеи-Камиона]]===
