112
правок
Изменения
Доказательство теоремы J Bondy завершено
}}
'''Предпосылки к теореме'''. [https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem#Mantel's_theorem Теорема Мантела](частный случай [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 теоремы Турана]) утверждает, что для любой граф на <tex> n </tex> вершинах, у которого количество ребер не меньше <tex> n^2 / 4 </tex>, либо содержит треуголник либо является <tex>K_{n / 2, n / 2}</tex>.
{{Теорема
*<tex> j + 2 \leqslant k \leqslant j + l - 2 </tex> : <tex>(v_j, v_k) \in E </tex> и <tex>(v_{j+1}, v_{k-l+1}) \notin E </tex>
Пусть <tex> G </tex> не <tex> K_{n/2, n/2} </tex>, тогда существует такое четное число <tex> k </tex>, что в графе <tex> G </tex> существует ребро <tex> (v_j, v_{j+k}) </tex>.Докажем, что в таком случае существует ребро <tex> (v_j, v_{j+2}) \in E </tex>.Пусть это не так и минимальное четное <tex> k </tex>, что <tex> \exists (v_j, v_{j+k}) \in E </tex> больше двух, т.е. <tex> k \geqslant 4 </tex>. Тогда существует три случая:
# <tex> 4 \leqslant k \leqslant n - l </tex> <br> <tex> (v_j, v_{j+k}) \in E \Rightarrow (v_{j+1}, v_{j+k+l-3}) \notin E \Rightarrow (v_{j+2}, v_{j+k}) \in E </tex> <br> <tex> \exists l = k-2 : (v_i, v_{i+l}) \in E </tex> - противоречие с минимальностью <tex> k </tex> # <tex> n - l + 2 \leqslant k \leqslant 2n - 2l </tex> <br> <tex> (v_j, v_{j+k}) \in E \Rightarrow (v_{j-1}, v_{j+k+l-1}) \notin E \Rightarrow (v_{j-2}, v_{j+k+2l-4}) \in E </tex> <br> однако <tex> 2n - k - 2l + 2 \leqslant k - 2 </tex> - противоречие с минимальностью <tex> k </tex> # <tex> 2n - 2l + 2 \leqslant k \leqslant n - 2 </tex> <br> <tex> (v_j, v_{j+k}) \in E \Rightarrow (v_{j-1}, v_{j+k+l-1}) \notin E \Rightarrow (v_{j-2}, v_{j+k+2l-2}) \in E </tex> <br> однако <tex> k + 2l - 2n \leqslant k - 2 </tex> - снова проиворечие с минимальностью выбранного k
Таким образом, в <tex> G </tex> существует ребро <tex> (v_j, v_{j+2}) </tex>, но тогда <tex> (v_j, v_{j+l}) \notin E </tex>, а следовательно <tex> (v_{j+1}, v_{j+3}) \in E </tex>. Если продолжить по всему графу, то получим, что <tex> \forall j : (v_j, v_{j+2}) \in E </tex> и, как следствие, <tex> G </tex> - панциклический.
}}
