Теорема Татта о существовании регулярного графа заданного размера с заданным обхватом
Версия от 22:26, 14 ноября 2017; KokorinIlya (обсуждение | вклад)
Определение: |
Обхват(англ. girth) графа | (обозначается ) — это длина наименьшего простого цикла в графе
Теорема (В. Татт, о существовании регулярного графа заданного размера с заданным обхватом): |
Пусть , причём чётно. Тогда существует -регулярный граф c обхватом и количеством вершин |
Доказательство: |
Доказательство: Пусть — семейство всех графов с вершинами, обхватом и максимальной степенью вершин не более . При > очевидно, что : например, этому множеству принадлежит граф, состоящий из простого цикла на вершинах и изолированных вершин.Пусть — количество вершин степени меньше в графе , а — максимальное из расстояний между парами вершин степени менее в графе . (при , положим ). Выберем в граф следующим образом: сначала выберем все графы с максимальным количеством рёбер, затем из них выберем графы с максимальным , и, наконец, из оставшихся выберем граф c максимальным .Докажем, что — регулярный граф степени .Предположим, что это не так и рассмотрим пару его максимально удаленных вершин степени менее Если : пусть это будут вершины и (если вершина степени менее в графе всего одна, то ). , то соединим их ребром и получим граф , при этом (так как в графе есть все те рёбра, которые есть в , и ребро ). Значит, граф не может быть выбран из множества , так как у него не максимальное количество рёбер. |