137
правок
Изменения
Нет описания правки
Степени всех остальных вершин в <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>.
Докажем, что <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>, получаем
<center> <tex> dist_{G'}(y, u) = dist_G(y, u) \geqslant g - 1 > dist_G(y, x) </tex> </center>
Значит, <tex>P</tex> проходит по ребру <tex>zx</tex>. Следовательно, <tex>P</tex> содержит путь по рёбрам графа <tex>G</tex> от y до одной из вершин <tex>x</tex> или <tex>z</tex> и ребро <tex>xz</tex>. Тогда
<center> <tex> dist_{G'}(y, u) = \min(dist_G(y, x), dist_G(y, z)) + 1 > dist_G(y, x) </tex>, </center>
так как <tex>dist_G(y, z) \geqslant g > dist_G(y, x)</tex>. Таким образом
<center> <tex> dist_{<k}(G') \geqslant dist_{G'}(y, u) > dist_G(y, x) dist_{<k}(G) </tex> </center>
Получили противоречие с принципом выбора графа <tex>G</tex>, что доказывает, что <tex>G</tex> {{---}} <tex>k</tex>{{---}}регулярный.
}}
==Источники информации==
* Карпов В. Д. - Теория графов, стр 108
