Hacker News Digest

Каждый несвязный без мостов граф содержит набор циклов, покрывающих каждую дугу ровно дважды. Для доказательства достаточно рассмотреть кубические (3‑регулярные) графы без мостов. Такие графы всегда обладают ничтожным 8‑потоком, что эквивалентно наличию ничтожного потока над полем Γ=𝔽₂³. На основе этого потока строится раскладка ребер множествами из двух элементов Γ так, чтобы у каждой вершине каждый элемент Γ встречался либо 0, либо 2 раза. Эта «расслабленная» 3‑красочная раскладка приводит к требуемому покрытию.

Для каждой вершины локально выбираются три элемента Γ из значений потока на её трёх инцидентных ребрах; из них формируются пары {t, t+x}, {t+x, t+z}, {t, t+z}. На каждом ребре эти пары совпадают, если выполнена система линейных уравнений над Γ⊕𝔽₂, которая всегда имеет решение (лемма 2.2). После выбора параметров t_v и ε_e получаем для каждого ребра набор из двух элементов Γ, удовлетворяющий условию (1). По построению множества M_s={e:s∈P_e} разбиваются на циклы, каждый элемент Γ появляется в ровно двух M_s около любой вершины, а их объединение покрывает все ребра двойным циклом. Таким образом любой безмостовой граф имеет цикл‑двойное покрытие.