210
правок
Изменения
м
}}
===Теорема Поша===
{{Теорема
|statement=
Пусть граф G имеет <tex>n \geq 3</tex> вершин. Если для всякого <tex>k,\, 1 \leq k < (n-1)/2</tex> число вершин со степенями, не превосходящими <tex>k</tex>, меньше чем <tex>k</tex>, и для нечетного <tex>n</tex> число вершин степени <tex>(n-1)/2</tex> не превосходит <tex>(n-1)/2</tex>, то G - гамильтонов граф.
Нет описания правки
<center><tex> d_k \leq k < n/2 \Rightarrow d_{n - k} \geq n - k, (*) </tex></center>
то граф <tex> G </tex> [[Гамильтоновы графы|гамильтонов]].
}}
