Изменения

1) Если <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>, так как у него не максимальное количество рёбер.

2) Так <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) + ... + (k - 1)^{g - 1} = \sum\limits_{n=10}^{g - 1} (k - 1)^n = \dfrac{(k-1)^{g} - 1}{k - 2}</tex> вершин графа, а на расстоянии не более <tex>g - 2</tex> от <tex>x</tex> находится не более чем <tex>1 + (k - 1) + ... + (k - 1)^{g - 2} = \sum\limits_{n=10}^{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>. Невозможно, что  Рассмотрим случай 2а) <tex>d_G(z) < k</tex>, так как в . В таком случае, <tex>d_G(z) < k, d_G(y) < k, dist_G(y, z) \geqslant g</tex> (невозможность чего следует из рассмотренного выше, что невозможно, согласно пункту 1. В таком случае: 2б). Следовательно, <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> Пусть <tex>G' = G \setminus zu \cup zx</tex>. Из <center> <tex> dist_G(y, u) \geqslant dist_G(y, z) - 1 \geqslant g - 1 > dist_G(x, y) = dist_{<k}(G) ~~~ \textbf{(1)} </tex>. </center> Следует, что <tex>d_G(u) = k</tex> <tex>g(G') = g(G) = g, |E(G')| = |e(G)| - 1 + 1 = |E(G)| </tex> <center> <tex> d_{G'}(x) = d_G(x) + 1 \leqslant k, d_{G'}(u) = d_G(u) - 1 = k - 1 ~~~ \textbf{(2)} </tex>. </center>  Степени всех остальных вершин в <tex>G</tex> и <tex>G'</tex> совпадают. Тогда <tex>G' \in G_{set}(g, n, k)</tex>. Из <tex>\textbf{(2)}</tex> следует, что <tex>v_{<k}(G') \geqslant v_{<k}(G)</tex>. Тогда ввиду выбора графа <tex>G</tex> должно быть <tex>v_{<k}(G') = v_{<k}(G)</tex>, что возможно лишь при <tex> d_{G'}(x) = k</tex> и <tex>d_G(x) = k - 1,/tex>. Так как <tex>kn</tex> чётно, вершина <tex>x</tex> не может быть единственной вершиной степени менее <tex>k</tex> в графе <tex>G</tex>, поэтому <tex>x \neq y</tex>.