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

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

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

Доказательство: Пусть [math]G_{set}(g, n, k)[/math] — семейство всех графов с [math]n[/math] вершинами, обхватом [math]g[/math] и максимальной степенью вершин не более [math]k[/math]. При [math]n[/math] > [math]g[/math] очевидно, что [math]G_{set}(g, n, k) \neq \emptyset[/math]: например, этому множеству принадлежит граф, состоящий из простого цикла на [math]g[/math] вершинах и [math]n - g[/math] изолированных вершин. Пусть [math]v_{\lt k}(G)[/math] — количество вершин степени меньше [math]k[/math]в графе [math]G[/math], а [math]dist_{\lt k}(G)[/math] — максимальное из расстояний между парами вершин степени менее [math]k[/math] в графе [math]G[/math]. (при [math]v_{\lt k}(G) \lt 2[/math], положим [math]dist_{\lt k}(G) = 0[/math]). Выберем в [math]G_{set}(g, n, k)[/math] граф следующим образом: сначала выберем все графы с максимальным количеством рёбер, затем из них выберем графы с максимальным [math]v_{\lt k}[/math], и, наконец, из оставшихся выберем граф [math]G[/math] c максимальным [math]dist_{\lt k}(G)[/math]. Докажем, что [math]G[/math] — регулярный граф степени [math]k[/math]. Предположим, что это не так и рассмотрим пару его максимально удаленных вершин степени менее [math]k[/math]: пусть это будут вершины [math]x[/math] и [math]y[/math] (если вершина степени менее [math]k[/math] в графе всего одна, то [math]x = y[/math]). Если [math]dist_G(x, y) \geqslant g - 1[/math], то соединим их ребром и получим граф [math]G' = G \cup xy, G'\in G_{set}(g, n, k)[/math], при этом [math]|E(G')| \gt |E(G)|[/math] (так как в графе [math]G'[/math] есть все те рёбра, которые есть в [math]G[/math], и ребро [math]xy[/math]). Значит, граф [math]G[/math] не может быть выбран из множества [math]G_{set}(g, n, k)[/math], так как у него не максимальное количество рёбер. Так [math]d_G(x), d_G(y) \leqslant k - 1 [/math], а степени остальных вершин графа не более [math]k[/math], то на расстоянии не более [math]g - 1[/math] от [math]y[/math] находится не более чем [math]1 + (k - 1) + ... + (k - 1)^{g - 1} = \sum\limits_{n=1}^{g - 1} (k - 1)^n = \dfrac{(k-1)^{g} - 1}{k - 2}[/math] вершин графа, а на расстоянии не более [math]g - 2[/math] от [math]x[/math] находится не более чем [math]1 + (k - 1) + ... + (k - 1)^{g - 2} = \sum\limits_{n=1}^{g - 2} (k - 1)^n =\dfrac{(k-1)^{g - 1} - 1}{k - 2}[/math] вершин. Тогда по условию теоремы существует такая вершина [math]z[/math], что [math]dist(x, z) \geqslant g - 1[/math] и [math]dist(y, z) \geqslant g[/math]. Невозможно, что [math]d_G(z) \lt k[/math], так как в таком случае, [math]d_G(z) \lt k, d_G(y) \lt k, dist_G(y, z) \geqslant g[/math] (невозможность чего следует из рассмотренного выше). Следовательно, [math]d_G(z) = k \geqslant 3[/math], следовательно, существует ребро [math]zu \in E(G)[/math], через которое проходят не все простые циклы длины [math]g[/math] графа [math]G[/math], тогда [math]g(G \setminus zu) = g(G) = g[/math]

[math]\triangleleft[/math]