Теорема Дирака
Версия от 05:02, 14 октября 2010; Roman Livarsky (обсуждение | вклад)
| Теорема: |
Если и для любой вершины неориентированного графа , то - гамильтонов граф. |
| Доказательство: |
| По теореме Хватала: для верна импликация |
| Теорема: |
Если [math]\ n \gt 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] |
