Теорема Дирака

Теорема:

Если [math]\ n \gt 3[/math] и [math]deg\ v \ge n/2[/math] для любой вершины [math]\ v[/math] графа G, то G - гамильтонов граф

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

[math]\triangleright[/math]

По теореме Хватала: для [math]\forall k[/math] верна импликация [math]d_k \le k \lt n/2 \Rightarrow d_{n-k} \ge n-k[/math]

[math]\triangleleft[/math]