137
правок
Изменения
Нет описания правки
|author = В. Татт
|about = о существовании регулярного графа заданного размера с заданным обхватом
|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>-[[Основные определения теории графов#def_undirected_graph_2 defFullGraph | регулярный граф]] <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 > g</tex> очевидно, что <tex>G_{set}(g, n, k) \neq \emptyset</tex>: например, этому множеству принадлежит граф, состоящий из простого цикла на <tex>g</tex> вершинах и <tex>n - g</tex> изолированных вершин.
