54
правки
Изменения
Нет описания правки
|proof=
Пусть, от противного, существует граф '''G''', который удовлетворяет условию теоремы, но не является гамильтоновым графом.Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф '''G''''.В силу того, что мы только добавляли ребра, условие теоремы не нарушилось. Пусть <math>\ u,v</math> несмежные вершины в полученном графе '''G''''. Если добавить ребро <math>\ uv</math>, появится гамильтонов цикл. Тогда путь <math>\ (u,v)</math> - гамильтонов. Для вершин <math>\ u,v</math> выполнено <math>deg\ u + deg \ v \ge n</math>. По принципу Дирихле, найдутся две смежные вершины <math>\ t_1,t_2</math> на пути <math>\ (u,v)</math> ,т.е. <math>\ u..t_1t_2..v</math> , такие, что существует ребро <math>\ ut_2</math> и ребро <math>\ t_1v</math>.Получили противоречие, т.к. <math>\ u..t_1t_2..v</math> - гамильтонов цикл.
}}
