Изменения

Пусть <tex>G' = G \setminus zu \cup zx</tex>. Из

Следует, что <tex>d_G(u) = k</tex>

<tex>g(G') = g(G) = g, |E(G')| = |e(G)| - 1 + 1 = |E(G)| </tex>

Докажем, что <tex>dist_{G'}(y, u) > dist_{G}(y, x)</tex>. Действительно, рассмотрим путь <tex>P: y \leadsto u</tex>, который реализует расстояние между <tex>y</tex> и <tex>u</tex> в <tex>G'</tex>. Если <tex>P</tex> проходит только по рёбрам <tex>G</tex>, то, учитывая <tex>\textbf{(1)}</tex>, получаем

Значит, <tex>P</tex> проходит по ребру <tex>zx</tex>. Следовательно, <tex>P</tex> содержит путь по рёбрам графа <tex>G</tex> от <tex>y</tex> до одной из вершин <tex>x</tex> или <tex>z</tex> и ребро <tex>xz</tex>. Тогда

так как <tex>dist_G(y, z) \geqslant g > dist_G(y, x)</tex>. Таким образом

Получили противоречие с принципом выбора графа <tex>G</tex>, что доказывает, что <tex>G</tex> {{---}} <tex>k</tex>-регулярный.