1632
правки
Изменения
м
rollbackEdits.php mass rollback
Имеем: <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} u + \operatorname{deg} v \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 \mid : ut_{i+1}\in EG</tex> и <tex> t_iv \in EG.</tex>
Получили противоречие, т. к. <tex>u \dots t_1v \dots t_2u</tex> {{---}} гамильтонов цикл.
}}
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Гамильтоновы графы]]
