Двойное покрытие циклами в теории графов — множество циклов в неориентированном графе, которое включает в себя каждое ребро ровно два раза. Например, любой полиэдральный граф образован из вершин и рёбер выпуклого многогранника, грани же при этом образуют двойное покрытие циклами: каждое ребро принадлежит ровно двум граням.

Дьёрдь Секереш и Пол Сеймур выдвинули гипотезу о двойном покрытии циклами, согласно которой для любого графа без мостов существует двойное покрытие циклами. Эту гипотезу можно эквивалентно переформулировать в терминах вложений графов, и в этой области она также известна как гипотеза о круговом вложении ( или ).

10 июля 2026 года компания OpenAI опубликовала препринт с заявленным положительным решением гипотезы, полностью сгенерированным языковой моделью GPT-5.6 Sol Ultra.

Формулировка Обычно гипотезу формулируют следующим образом: верно ли, что в любом графе без мостов есть набор простых циклов, для которого каждое ребро содержится ровно в двух циклах этого набора? Требование отсутствия в графе мостов является необходимым, поскольку никакой из мостов не может принадлежать какому-либо из циклов. Набор циклов, который удовлетворяет условию гипотезы, называется двойным покрытием циклами. Некоторые графы, типа циклических или кактусов, могут быть покрыты только с повторным использованием некоторых циклов, поэтому такого рода повторения циклов разрешены в двойном покрытии циклами.

Предложенное решение 10 июля 2026 года компания OpenAI выложила в открытый доступ трёхстраничный препринт с доказательством гипотезы, созданным моделью GPT-5.6 Sol Ultra, а также двухстраничный промпт, использованный для его генерации. В промпте модели предписывалось задействовать «до 64 параллельных агентов», применять состязательных агентов для постоянной валидации и проверки гипотез на ошибки, а также потратить на решение задачи «не менее 8 часов». Команда OpenAI также опубликовала полную формализацию доказательства на языке Lean.

В доказательстве используется сведение Игера (1985), согласно которому гипотезу достаточно доказать для кубических мультиграфов без петель (где степень каждой вершины равна 3). Кроме того, решение опирается на факт, что каждый граф без мостов допускает нигде не равный нулю -поток, что было независимо установлено Игером (1976) и Килпатриком (1975).

Сведение к снаркам У снарка (кубического графа без мостов, в котором рёбра нельзя покрасить в три цвета так, чтобы два ребра одного цвета не сходились в одной вершине) по теореме Визинга будет хроматический индекс 4. Снарки являются самыми сложными графами для двойного покрытия циклами: если гипотеза справедлива для снарков, то она будет верна для всех графов без мостов.

Действительно: если в графе есть вершина степени 1, то её ребро образует мост. Если есть вершина степени 2, то можно выкинуть эту вершину из графа, а её ребра объединить в одно. Если допустить, что в графе есть вершина степени 4 или больше, тогда можно найти два таких ребра и , смежных с этой вершиной, что их можно удалить, а вместо них добавить ребро, соединяющее концы этих рёбер, отличные от , сохранив при этом свойство, что в графе нет мостов. Из двойного покрытия нового графа легко получить двойное покрытие для старого графа.

Если у кубического графа при этом хроматический индекс 3, то легко строится двойное покрытие циклами: в первый цикл попадают все рёбра первого и второго цвета, во второй цикл — все рёбра первого и третьго цвета, а в третий цикл — все рёбра второго и третьего цвета.

Сводимые конфигурации На сегодняшний день было предложено несколько подходов к решению гипотезы. Один из таких подходов заключается в том, что мы покажем, что не существует минимального контрпримера, а именно, будем искать сводимые конфигурации в каждом графе. Сводимая конфигурация — это подграф, который можно заменить меньшим подграфом так, что мы сохраним свойство наличия или отсутствия двойного покрытия циклами (подобный подход был с успехом применён в доказательстве теоремы о четырёх красках). Например, если в графе найдётся треугольник (три вершины, соединённые друг с другом), то мы сможем провести преобразование треугольник-звезда, тем самым уменьшив число вершин на 2; при этом любое двойное покрытие циклами меньшего графа преобразуется в покрытие для изначального большего графа. Таким образом, в минимальном контрпримере к гипотезе мы не сможем обнаружить подграф в виде треугольника. Также, например, с помощью компьютера было показано, что в минимальном контрпримере (который будет кубическим графом) не может быть цикла длиной 11 или меньше, то есть обхват такого графа будет как минимум 12.

К сожалению, в отличие от вышеупомянутой теоремы о четырёх красках, для гипотезы о двойном покрытии циклами не существует конечного набора сводимых конфигураций. Например, в каждой сводимой конфигурации найдётся какой-нибудь цикл, поэтому для любого конечного набора сводимых конфигураций найдётся такое число γ, что в любой конфигурации есть цикл длиной меньшей γ. Но известно, что существуют снарки с произвольно высоким обхватом (длиной минимального цикла). Такой снарк не получится уменьшить, так как ни одна из конфигураций в нём не содержится, и наша стратегия будет неприменима к данному примеру.

Гипотеза о цепном вложении

Примечания

Литература

Ссылки Cycle double cover conjecture, circular embedding conjecture, и Grünbaum’s conjecture, с сайта Open Problem Garden. The Cycle Double Cover Conjecture, Dan Archdeacon.

Категория:Теория графов Категория:Топологическая теория графов Категория:Гипотезы