210
правок
Изменения
м
Нет описания правки
Если <tex> n > 3 </tex> и <tex> \deg v \geqslant n/2 </tex> для любой вершины <tex> v </tex> графа <tex> G </tex>, то <tex> G </tex> {{---}} гамильтонов граф.
|proof =
Возьмем любые несмежные вершины <tex> u, v \in G </tex>.
Тогда <tex> \displaystyle \deg u + \deg v \geqslant \frac n 2 + \frac n 2 = n </tex>.
