Теорема Татта о существовании регулярного графа заданного размера с заданным обхватом

Материал из Викиконспекты
Версия от 19:34, 14 ноября 2017; KokorinIlya (обсуждение | вклад) (Новая страница: «{{Теорема |id = thMain. |author = В. Татт |about = о существовании регулярного графа заданного размера ...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Теорема (В. Татт, о существовании регулярного графа заданного размера с заданным обхватом):
Пусть [math] k, g, n \in [/math] [math] \mathbb{N} [/math], причём [math] k, n \geqslant 3, n \gt \dfrac{k(k-1)^{g-1} - 2}{k - 2}, kn [/math] чётно. Тогда существует [math]k[/math]-регулярный граф [math]G[/math] c обхватом [math]g(G) = g[/math] и количеством вершин [math] |V| = n[/math]
Доказательство:
[math]\triangleright[/math]
доказательство (необязательно)
[math]\triangleleft[/math]