137
правок
Изменения
Нет описания правки
|statement = Пусть <tex> k, g, n \in </tex> <tex> \mathbb{N} </tex>, причём <tex> k, n \geqslant 3, n > \dfrac{k(k-1)^{g-1} - 2}{k - 2}, kn </tex> чётно. Тогда существует <tex>k</tex>-регулярный граф <tex>G</tex> c обхватом <tex>g(G) = g</tex> и количеством вершин <tex> |V| = n</tex>
|proof = Доказательство:
Пусть <tex>G_{set}(g, n, k)</tex> {{---}} семейство всех графов с <tex>n</tex> вершинами, обхватом <tex>g</tex> и максимальной степенью вершин не более <tex>k</tex>. При <tex>n</tex> > <tex>g</tex> очевидно, что <tex>G_{set}(g, n, k) \neq \emptyset</tex>: например, этому множеству принадлежит граф, состоящий из простого цикла на <tex>g</tex> вершинах и <tex>n - g</tex> изолированных вершин. Пусть <tex>v_{<k}(G)</tex> {{---}} количество вершин степени меньше <tex>k</tex>в графе <tex>G</tex>, а <tex>dist_{<k}(G)</tex> {{---}} максимальное из расстояний между парами вершин степени менее <tex>k</tex> в графе <tex>G</tex>. (при <tex>v_{<k}(G) < 2</tex>, положим <tex>dist_{<k}(G) = 0</tex>). Выберем в <tex>G_{set}(g, n, k)</tex> граф следующим образом: сначала выберем все графы с максимальным количеством рёбер, затем из них выберем графы с максимальным <tex>v_{<k}</tex>, и, наконец, из оставшихся выберем граф <tex>G</tex> c максимальным <tex>dist_{<k}(G)</tex>.
Докажем, что <tex>G</tex> {{---}} регулярный граф степени <tex>k</tex>.
