Изменения

|proof=[[Файл:Лемма к Татту.png|300px|thumb|left|Иллюстрация к теореме для <tex>k = 4</tex>. У вершины <tex>x</tex>(чёрной) не более <tex>k - 1 = 3</tex> соседей (синих вершин), у каждой из <tex>k - 1</tex> синих вершин не более <tex>k - 1</tex> нерассмотренных соседей (красных вершин), то есть красных вершин не более <tex>(k - 1)^2</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> |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>.