Теорема Дирака
Версия от 05:13, 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] |
