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