Теорема Дирака — различия между версиями

Версия 05:02, 14 октября 2010

Теорема:

Если и для любой вершины неориентированного графа , то - гамильтонов граф.

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

По теореме Хватала: для верна импликация

@@ Строка 1: / Строка 1: @@
 {{Теорема
 |statement=
-Если <math>\ n > 3</math> и <math>deg\ v \ge n/2</math>  для любой вершины <math>\ v</math> неориентированного графа  '''G''', то  '''G''' - гамильтонов граф.
+Если <tex>\ n > 3</tex> и <tex>deg\ v \ge n/2</tex>  для любой вершины <tex>\ v</tex> неориентированного графа  <tex>\ G</tex>, то  <tex>\ G</tex> - гамильтонов граф.
 |proof=
-По теореме Хватала: '''для''' <math>\forall k</math> '''верна импликация''' <math>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</math>
+По [[Теорема Хватала|теореме Хватала]]: для <tex>\forall k</tex> верна импликация <tex>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</tex>
 }}