137
правок
Изменения
→Лемма о существовании вершины на заданном расстоянии
{{Лемма
|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>.
}}
