Изменения

Если <tex>n \ge geqslant 3</tex> и <tex>\operatorname{deg\ } u + \operatorname{deg\ } v \ge geqslant n</tex> для любых двух различных несмежных вершин <tex>u</tex> и <tex>v</tex> [[Основные определения теории графов#Неориентированные графы|неориентированного графа ]] <tex>G</tex>, то <tex>G</tex> {{---}} [[Гамильтоновы графы | гамильтонов граф]].

Для вершин <tex>u,v</tex> выполнено <tex>\operatorname{deg\ } u + \operatorname{deg\ } v \ge geqslant n.</tex>

По принципу Дирихле всегда найдутся две смежные вершины <tex> t_1,t_2</tex> на пути <tex>(u,v)</tex>, т.е. <tex>u..\dots t_1t_2..\dots v</tex> , такие, что существует ребро <tex>ut_2</tex> и ребро <tex>t_1v.</tex>

Действительно, пусть <tex>S=</tex> { <tex> \{ i| \mid e_i=ut_{i+1} \in EG\}</tex> } и <tex>T = </tex> { <tex> \{ i| \mid f_i=t_iv \in EG\}</tex> }

Имеем: <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg\ } u + \operatorname{deg\ } v \ge geqslant n </tex>, но <tex>\left\vert S + T \right\vert < n.</tex>

Тогда <tex>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</tex> , т.е. <tex>\exists i| : ut_{i+1}\in EG</tex> и <tex> t_iv \in EG.</tex>Получили противоречие, т.к. <tex>u..\dots t_1v..\dots t_2u</tex> {{---}} гамильтонов цикл.

== См. также ==* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]* [[Теорема Дирака]]== Источники информации ==1. * Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />2. * Харари {{---}} Теория графов. '''ISBN 978-5-397-00622-4'''