112
правок
Изменения
добавлено забытое
|proof=По [https://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9E%D1%80%D0%B5 теореме Оре] <tex> G </tex> - гамильтонов граф. Покажем, что <tex> m \geqslant n^2/4 </tex>. Пусть <tex> k </tex> - минимальная степень вершины в графе.
# <tex> k \geqslant n/2 </tex>, тогда <tex> 2m = \sum\limits_{i=1}^n deg(v_i) >= \sum\limits_{i=1}^n k = k * n \geqslant n^2/2 </tex>
# <tex> k < n/2 </tex>. Пусть существует x вершин, так что их степени равны <tex> k </tex>, тогда они все должна быть связаны, так как иначе мы получим противоречие с утверждением теоремы <tex> \forall (u, v) \notin E : deg(u) + deg(v) \geqslant n </tex>. Понятно, что <tex> x \leqslant k + 1 </tex>, но так как граф является гамильтоновым, то он связен, а значит <tex> x < k + 1 </tex> .А также есть как минимум <tex> n - k - 1 </tex> стпени которых как минимум <tex> n - k </tex>.Тогда можно оценить количество ребер.<br> <tex> m \geqslant \genfrac{}{}{}{}{1}{2}((n-k-1)(n-k)+k^2+k+1) = \genfrac{}{}{}{}{1}{2}(n^2 - n(2k + 1) + 2k^2 + 2k + 1) \geqslant \genfrac{}{}{}{}{n^2+1}{4} </tex>
}}
