Изменения

Степени всех остальных вершин в <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>.

}}