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