Теорема Оре

Теорема:

Если [math]n \ge 3[/math] и [math]deg\ u + deg \ v \ge n[/math] для любых двух различных несмежных вершин [math]\ u[/math] и [math]\ v[/math] графа G, то G - гамильтонов граф.

Доказательство:

[math]\triangleright[/math]

...

[math]\triangleleft[/math]