ГРАФОВАЯ ГОЛОВОЛОМКА 1960-Х НАКОНЕЦ РЕШЕНА

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

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

Гипотеза

В 1960-х годах Эрдёш и Галлаи предположили, что рёбра любого графа с n вершинами можно разбить на циклы и отдельные рёбра, число которых не более чем пропорционально n, — записывается O(n). Эрдёш включал эту гипотезу в несколько своих сборников открытых проблем. Родственная гипотеза Хайоша требует не более (n − 1)/2 циклов в любом эйлеровом графе.

Линейная оценка — лучшее, на что можно надеяться: Эрдёш показал, что некоторым графам нужно около 1,5 n частей. Вопрос был в том, всегда ли достаточно некоторой константы, умноженной на n.

Пятьдесят лет медленно ползущих оценок

Сами Эрдёш и Галлаи заметили простой метод: раз за разом удалять самый длинный цикл. Он даёт около n log n частей — и, согласно статье, эта оценка оставалась лучшей общей почти пятьдесят лет. Позже Конлон, Фокс и Судаков снизили её до n log log n, затем Бучич и Монтгомери — до n log* n, где log* n — сколько раз нужно взять логарифм, чтобы опуститься ниже единицы, — растёт невообразимо медленно. Эти подходы работали раундами, и каждый раунд стоил около n циклов, поэтому число раундов всегда просачивалось в итоговый счёт. Кроме того, гипотезу доказали для особых семейств, например для случайных графов.

Веса, которые платят за петли

Чжэхун Ким из KAIST в Южной Корее теперь доказывает гипотезу: существует фиксированная константа C, такая что любой граф с n вершинами разбивается не более чем на Cn циклов и рёбер. Как следствие, гипотеза Хайоша верна с точностью до постоянного множителя.

Доказательство отказывается от раундов. Единая процедура удаляет циклы и рёбра по одному, а общее число контролируется двумя величинами, каждая из которых остаётся ниже константы, умноженной на n.

• Потенциал, основанный на степенях. Каждая вершина получает вес, который уменьшается с ростом числа её рёбер, примерно 1 / (степень × log² степени). Цикл называется тяжёлым, если веса его вершин в сумме дают не меньше 1. Удаление тяжёлого цикла снижает общий «потенциал» как минимум на 1, а изначально этот потенциал не превышает константы, умноженной на n. Значит, тяжёлые циклы можно удалить лишь O(n) раз.
• Число вершин. Когда тяжёлых циклов не остаётся, граф «лёгкий» — и главная новая теорема показывает, что лёгкий граф с большими степенями обязан содержать плотную, почти замкнутую область. Эту область разбивают на число циклов и рёбер, пропорциональное её размеру, после чего как минимум у пятидесятой части её вершин остаётся не более двух рёбер, и они выбывают навсегда. Поскольку каждая вершина может выбыть лишь один раз, эта часть тоже стоит O(n).

Внутри плотных частей графа куски путей замыкаются в один цикл соединяющими путями, проложенными через «экспандеры»; случайная раскраска не даёт соединяющим путям одного цикла пересекаться. — Рисунок 3, Kim (2026), arXiv:2610.07840.

Чтобы разбить эти плотные области, доказательство расширяет инструментарий Бучича и Монтгомери на основе устойчивых «экспандеров» — графов, в которых у любого множества вершин много соседей, — и раскрашивает вершины случайным образом, чтобы соединяющие пути одного и того же цикла никогда не сталкивались.

Что остаётся открытым

Константа C огромна, и автор не пытался её оптимизировать. Найти наилучшую константу — не меньше 1,5 — пока не удалось; открытыми остаются и точная гипотеза Хайоша, и родственная гипотеза Галлаи о разбиении графов на пути. Приёму с весами нужны лишь веса со сходящейся суммой, и автор предполагает, что он может пригодиться и в других задачах о разложении.

Это препринт одного автора, ещё не проверенный рецензированием.

Конфликт интересов. Автор сообщает, что активно использовал ChatGPT (OpenAI) и Claude (Anthropic) при разработке рассуждений и подготовке текста и рисунков, что проверил все результаты и несёт полную ответственность за статью. Текст, который вы читаете, тоже написан Claude.