137
правок
Изменения
Нет описания правки
}}
==Лемма о существовании вершины на заданном расстоянии==
{{Лемма
|about=существовании вершины на заданном расстоянии
|statement= Пусть <tex> k, g \in \mathbb{N} </tex>, причём <tex> k \geqslant 3</tex>, <tex>G</tex>{{---}}граф, <tex>|V(G)| > \dfrac{k(k-1)^{g-1} - 2}{k - 2} </tex>, <tex>\forall v \in V(G) : d_G(v) \leqslant k;</tex> <tex> x, y \in V(G), d_G(x), d_G(y) \leqslant k - 1</tex>, тогда существует такая вершина <tex>z</tex>, что <tex>dist(x, z) \geqslant g - 1</tex> и <tex>dist(y, z) \geqslant g</tex>.
|proof=Так как <tex>d_G(x), d_G(y) \leqslant k - 1 </tex>, а степени остальных вершин графа не более <tex>k</tex>, то на расстоянии не более <tex>g - 1</tex> от <tex>y</tex> находится не более чем <tex>1 + (k - 1) + \ldots + (k - 1)^{g - 1} = \sum\limits_{n=0}^{g - 1} (k - 1)^n = \dfrac{(k-1)^{g} - 1}{k - 2}</tex> вершин графа, а на расстоянии не более <tex>g - 2</tex> от <tex>x</tex> находится не более чем <tex>1 + (k - 1) + \ldots + (k - 1)^{g - 2} = \sum\limits_{n=0}^{g - 2} (k - 1)^n =\dfrac{(k-1)^{g - 1} - 1}{k - 2}</tex> вершин. Так как <tex>\dfrac{(k-1)^{g - 1} - 1}{k - 2} + \dfrac{(k-1)^{g} - 1}{k - 2} = \dfrac{k(k-1)^{g-1} - 2}{k - 2}</tex>, а <tex> |V(G)| > \dfrac{k(k-1)^{g-1} - 2}{k - 2}</tex>, то существует такая вершина <tex>z</tex>, которая не принадлежит ни одному из этих множеств, то есть <tex>dist(x, z) \geqslant g - 1</tex> и <tex>dist(y, z) \geqslant g</tex>.
}}
{{Теорема
|id = thMain.
|author = В. Татт
|proof = Доказательство:
Пусть <tex>G_{set}(g, n, k)</tex> {{---}} семейство всех графов с <tex>n</tex> вершинами, обхватом <tex>g</tex> и максимальной степенью вершин не более <tex>k</tex>. При <tex>n > g</tex> очевидно, что <tex>G_{set}(g, n, k) \neq \emptyset</tex>: например, этому множеству принадлежит граф, состоящий из простого цикла на <tex>g</tex> вершинах и <tex>n - g</tex> изолированных вершин.
# Если <tex>dist_G(x, y) \geqslant g - 1</tex>, то соединим их ребром и получим граф <tex>G' = G \cup xy, G'\in G_{set}(g, n, k)</tex>, при этом <tex>|E(G')| > |E(G)|</tex> (так как в графе <tex>G'</tex> есть все те рёбра, которые есть в <tex>G</tex>, и ребро <tex>xy</tex>). Значит, граф <tex>G</tex> не может быть выбран из множества <tex>G_{set}(g, n, k)</tex>, так как у него не максимальное количество рёбер.
# Так <tex>d_G(x), d_G(y) \leqslant k - 1 </tex>, а степени остальных вершин графа не более <tex>k</tex>, то на расстоянии не более <tex>g - 1</tex> от <tex>y</tex> находится не более чем <tex>1 + (k - 1) + \ldots + (k - 1)^{g - 1} = \sum\limits_{n=0}^{g - 1} (k - 1)^n = \dfrac{(k-1)^{g} - 1}{k - 2}</tex> вершин графа, а на расстоянии не более <tex>g - 2</tex> от <tex>x</tex> находится не более чем <tex>1 + (k - 1) + \ldots + (k - 1)^{g - 2} = \sum\limits_{n=0}^{g - 2} (k - 1)^n =\dfrac{(k-1)^{g - 1} - 1}{k - 2}</tex> вершин. Так как <tex>\dfrac{(k-1)^{g - 1} - 1}{k - 2} + \dfrac{(k-1)^{g} - 1}{k - 2} = \dfrac{k(k-1)^{g-1} - 2}{k - 2}</tex>, а <tex> n > \dfrac{k(k-1)^{g-1} - 2}{k - 2}</tex>, то по условию теоремы лемме существует такая вершина <tex>z</tex>, что <tex>dist(x, z) \geqslant g - 1</tex> и <tex>dist(y, z) \geqslant g</tex>.
## <tex>d_G(z) < k</tex>. В таком случае, <tex>d_G(z) < k, d_G(y) < k, dist_G(y, z) \geqslant g</tex>, что невозможно, согласно пункту 1. В таком случае:
## <tex>d_G(z) = k \geqslant 3</tex>, следовательно, существует ребро <tex>zu \in E(G)</tex>, через которое проходят не все простые циклы длины <tex>g</tex> графа <tex>G</tex>, тогда <tex>g(G \setminus zu) = g(G) = g</tex>
