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