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

Определение:

Обхват(англ. girth) графа [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]