137
правок
Изменения
Нет описания правки
Докажем, что <tex>G</tex> {{---}} регулярный граф степени <tex>k</tex>.
Предположим, что это не так и рассмотрим пару его максимально удаленных вершин степени менее <tex>k</tex>: пусть это будут вершины <tex>x</tex> и <tex>y</tex> (если вершина степени менее <tex>k</tex> в графе всего одна, то <tex>x =
y</tex>).
Если <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>, так как у него не максимальное количество рёбер.
}}
