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

Материал из Викиконспекты
Версия от 04:22, 10 октября 2010; Exlerok (обсуждение | вклад) (Новая страница: «{{Теорема |statement= Если <math>\ n > 3</math> и <math>deg\ v \ge n/2</math> для любой вершины <math>\ v</math> графа '''G''', т…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Теорема:
Если [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]