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

Теорема:

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

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

[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]

Источники

Харари Ф. - Теория графов. ISBN 978-5-397-00622-4