Изменения
frac -> genfrac
}}
'''Предпосылки к теореме'''. Теорема Мантела<ref>https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem#Mantel's_theorem</ref>(частный случай теоремы Турана<ref>https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A2%D1%83%D1%80%D0%B0%D0%BD%D0%B0</ref>) утверждает, что для любого граф на <tex> n </tex> вершинах, у которого количество ребер не меньше <tex> \genfrac{}{}{}{0}{n^2 / }{4 } </tex>, либо содержит треугольник либо является <tex>K_{\genfrac{}{}{}{}{n / }{2}, \genfrac{}{}{}{}{n / }{2}}</tex>.
{{Теорема
|about=J. A. Bondy
|statement=
<tex>G(V, E) </tex> {{---}} гамильтонов граф, <tex>|V| = n, |E| \geqslant \genfrac{}{}{}{0}{n^2/}{4 } </tex>.
Тогда верно одно из двух утверждений:
#<tex> G </tex> {{---}} панциклический граф
#<tex> G </tex> = <tex>K_{\genfrac{}{}{}{}{n / }{2}, \genfrac{}{}{}{}{n / }{2}}</tex>
|proof=
Докажем методом от противного, что <tex> n </tex> {{---}} четно. Пусть <tex> n </tex> является нечетным, тогда из рассуждений выше существует вершина <tex> v_x </tex>, для которое верно, что <tex> deg(v_x) \leqslant \genfrac{}{}{}{0}{n-1}{2} </tex>.
Пусть это не так, тогда <tex> \forall i, 1 \leqslant i \leqslant n : deg(v_i) \geqslant \genfrac{}{}{}{0}{n-1}{2} + 1 = \genfrac{}{}{}{0}{n+1}{2} </tex>, значит <tex> \forall j, 1 \leqslant j \leqslant n : deg(v_j) + deg(v_{j+1}) \geqslant \genfrac{}{}{}{0}{n+1}{2} + \genfrac{}{}{}{0}{n+1}{2} = n + 1 </tex>, то есть мы получили противоречие с тем, что <tex> deg(v_j) + deg(v_{j + 1}) \leqslant n </tex>.
Без потери общности пусть <tex> v_x = v_n </tex>. Рассмотрим <tex> 2|E| = \sum\limits_{i=1}^n deg(v_i) = \sum\limits_{i=1}^{(\genfrac{}{}{}{}{n - 1)/}{2}} (deg(v_{2i-1}) + deg(v_{2i})) + deg(v_n) \leqslant \genfrac{}{}{}{0}{n(n-1)}{2} + </tex> <tex> \genfrac{}{}{}{0}{n-1}{2} < \genfrac{}{}{}{0}{n^2}{2} </tex>, то есть <tex> |E| < \genfrac{}{}{}{0}{n^2}{4} </tex>, но по условию <tex> |E| \geqslant \genfrac{}{}{}{0}{n^2/}{4 } </tex> {{---}} получили противоречие. Таким образом <tex> n </tex> является четным. Тогда верно, что <tex> 2|E| \leqslant \sum\limits_{i=1}^n deg(v_i) = \sum\limits_{i=1}^{n/2} (deg(v_{2i-1}) + deg(v_{2i})) \leqslant \genfrac{}{}{}{0}{n^2}{2} </tex>, а так как по условию <tex> |E| \geqslant \genfrac{}{}{}{0}{n^2/}{4 } </tex>, то <tex> |E| = \genfrac{}{}{}{0}{n^2}{4} </tex>. Данное равенство достигается, если верно, что:
[[Файл:Circle 3.jpg|800px|right]]
Тогда верно одно из двух утверждений:
#<tex> G </tex> {{---}} панциклический граф
#<tex> G </tex> = <tex>K_{\genfrac{}{}{}{}{n / }{2}, \genfrac{}{}{}{}{n / }{2}}</tex>|proof=По [[Теорема Оре|теореме Оре]] <tex> G </tex> {{---}} гамильтонов граф. Покажем, что <tex> m \geqslant \genfrac{}{}{}{0}{n^2/}{4 } </tex>. Пусть <tex> k </tex> {{---}} минимальная степень вершины в графе. # <tex> k \geqslant \genfrac{}{}{}{0}{n/}{2 } </tex>, тогда <tex> 2m = \sum\limits_{i=1}^n deg(v_i) >= \sum\limits_{i=1}^n k = k n \geqslant \genfrac{}{}{}{0}{n^2/}{2 } </tex> # <tex> k < \genfrac{}{}{}{0}{n/}{2 } </tex>. Пусть существует <tex> x </tex> вершин, так что их степени равны <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> x </tex> вершин степени <tex> k </tex> провести оставшиеся ребра в одну вершину, у которой степень больше, то в графе остенется как минимум <tex> n - k - 1 </tex> вершин, степени которых как минимум <tex> n - k </tex>, поскольку должно выполняться неравенство из теоермы. Тогда можно оценить количество ребер. <br> <tex> m \geqslant \genfrac{}{}{}{0}{1}{2}((n-k-1)(n-k)+k^2+(k+1)) = \genfrac{}{}{}{0}{1}{2}(n^2 - n(2k + 1) + 2k^2 + 2k + 1) \geqslant \genfrac{}{}{}{0}{n^2+1}{4} </tex>
Таким образом <tex> m \geqslant \genfrac{}{}{}{0}{n^2/}{4 } </tex> и согласно теореме граф либо панциклический, либо <tex>K_{\genfrac{}{}{}{}{n / }{2}, \genfrac{}{}{}{}{n / }{2}}</tex>.
}}
