Нечётный граф

Если две вершины в O_n соответствуют множествам одинакового размера, отличающихся k элементами, то можно получить из первого второе за 2k шагов, на каждом шаге убирая или добавляя один элемент. Если 2k < n, то это кратчайший путь. В противном случае можно найти более короткий путь этого типа, если начать с дополнительного ко второму множества, а затем получить второе множество, сделав ещё один шаг. Таким образом, диаметр графа O_n равен n − 1[1][2].

Любой нечётный граф 3-дужно-транзитивен — любой ориентированный трёхрёберный путь в нечётном графе может быть переведён в любой такой же путь с помощью симметрии графа[13]. Нечётные графы дистанционно-транзитивны, поскольку они дистанционно-регулярны[2]. Как дистанционно-регулярные графы, они однозначно определяются их массивом пересечений — никакой другой дистанционно-регулярный граф не может иметь те же самые параметры, что и нечётный граф[14]. Однако вопреки высокой степени симметрии, нечётные графы O_n для n > 2 никогда не являются Графами Кэли[15].

Нечётные графы с n ≥ 3 имеют обхват шесть. Однако, хотя они и не являются двудольными графами, их нечётные циклы намного длиннее, а именно нечётный граф O_n имеет нечётный обхват 2n − 1. Если n-регулярный граф имеет диаметр n − 1, нечётный обхват 2n − 1 и только n различных собственных значений, он должен быть дистанционно-регулярным. Дистанционно-регулярные графы диаметра n − 1 и нечётного обхвата 2n − 1 известны как обобщённые нечётные графы и включают складные кубические графы так же, как и сами нечётные графы[5].

Пусть O_n — нечётный граф, определённый на (2n − 1)-элементных подмножествах множества X, и пусть x — элементы множества X. Тогда среди вершин O_n ровно ${\displaystyle {\tbinom {2n-2}{n-2}}}$ вершин соответствуют множествам, которые содержат x. Поскольку все эти множества содержат x, они не являются непересекающимися, и образуют независимое множество графа O_n. Таким образом, O_n имеет 2n − 1 различных независимых множеств размера ${\displaystyle {\tbinom {2n-2}{n-2}}}$. Из теоремы Эрдёша – Ко – Радо следует, что это максимальные независимые множеств графа O_n. Таким образом, число независимости графа O_n равно ${\displaystyle {\tbinom {2n-2}{n-2}}.}$ Более того, любое максимальное независимое множество должно иметь этот вид, так что O_n имеет в точности 2n − 1 максимальных независимых множеств[2].

Если I — максимальное независимое множество, образованное множеством содержащим элемент x, то дополнение множества I — это множество вершин, не содержащих x. Это дополнение порождает паросочетание в G. Каждая вершина независимого множества смежна n вершинам паросочетания, а каждая вершина паросочетания смежна n − 1 вершинам независимого множества[2]. Ввиду этого разложения и ввиду того, что нечётные графы не являются двудольными, они имеют хроматическое число равное трём — вершинам максимального независимого множества можно назначить один цвет, а два других цвета получим из паросочетания, порождённого дополнением.

По теореме Визинга число цветов, необходимых для раскраски рёбер нечётного графа O_n, равно либо n, либо n + 1, и в случае графов Петерсена O₃ оно равно n + 1. Если n — степень двух, число вершин в графе нечётно, откуда опять следует, что число цветов в рёберной раскраске равно n + 1[16]. Однако O₅, O₆ и O₇ могут быт раскрашены n цветами[2][16].

Биггс[10] объясняет эту задачу следующей историей: одиннадцать футболистов в придуманном городе Кроам хотят образовать пары команд для мини-футбола (один человек остаётся судить встречу) всеми 1386 различными способами и хотят составить расписание игр между всеми парами, при этом шесть игр каждой команды должны играться в разные дни недели, при отсутствии игр по воскресеньям. Возможно ли это? В этой истории каждая игра представляет ребро O₆, все дни представлены цветами, а рёберная раскраска в 6 цветов графа O₆ даёт расписание.

Граф Петерсена O₃ — это хорошо известные негамильтоновы графы, но было показано, что графы от O₄ до O₁₄ содержат гамильтоновы циклы[8][17][18][19]. Более строго, комбинируя задачи поиска гамильтоновых циклов и рёберной раскраски, можно разбить рёбра графа O_n (для n = 4, 5, 6, 7) на ближайшее снизу целое от (n/2) гамильтоновых циклов. Если n нечётно, оставшиеся рёбра образуют совершенное сочетание[2][16]. Для n = 8, нечётное число вершин в O_n не позволяет раскрасить рёбра в 8 цветов, но не закрывает возможность разложения на четыре гамильтоновых цикла.

Гипотеза Ловаса о гамильтоновом цикле предполагает, что каждый нечётный граф имеет гамильтонов путь и что каждый нечётный граф O_n с n ≥ 4 имеет гамильтонов цикл.