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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Обхват графа [math]G[/math](обозначается [math]g(G)[/math]) — это длина наименьшего цикла в графе [math]G[/math]


Теорема (В. Татт, о существовании регулярного графа заданного размера с заданным обхватом):
Пусть [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]
(coming soon)
[math]\triangleleft[/math]