Every bridgeless graph with mm edges is conjectured (Alon and Tarsi, 1985) to admit a cycle cover — a collection of cycles such that every edge lies in at least one of them — of total length at most 7m/5=1.4m7m/5=1.4m. The conjecture was raised as the open core of Candráková and Lukoťka's work on short cycle covers of cubic graphs (which proved a 1.6m1.6m bound for cubic graphs), together with the companion Cycle Double Cover Conjecture; the latter was resolved by a proof announced by OpenAI in July 2026, while the 7/57/5 length conjecture remains open. The constant 7/57/5 is best possible (the Petersen graph attains it), and the best current upper bounds are 212/135⋅m≈1.5703m212/135\cdot m\approx1.5703m for bridgeless cubic graphs and 5/3⋅m−(1/42)log⁡m5/3\cdot m-(1/42)\log m for arbitrary bridgeless graphs. The surviving open problem is whether the universal constant can be brought down to the sharp value 7/57/5.

Background

A graph is called bridgeless (2-edge-connected) if it has no bridge, i.e. no single edge whose deletion disconnects the graph; equivalently, every edge lies on a cycle, which is exactly the condition for a cycle cover to be possible. A cycle cover of a graph GG is a collection of cycles of GG such that every edge is contained in at least one of them, and its length is the sum of the lengths of the cycles. Writing m=∣E(G)∣m=|E(G)| and cc(G)cc(G) for the minimum total length of a cycle cover, Bermond, Jackson, and Jaeger (1983) and, independently, Alon and Tarsi (1985) proved that every bridgeless graph satisfies cc(G)≤5/3⋅mcc(G)\le 5/3\cdot m, and Alon and Tarsi conjectured the sharp bound cc(G)≤7/5⋅m=1.4mcc(G)\le 7/5\cdot m=1.4m. The constant cannot be lowered: the Petersen graph (the smallest bridgeless cubic graph that is not 3-edge-colourable) has m=15m=15 edges and shortest cycle cover of length exactly 21=7/5⋅1521=7/5\cdot 15. Cubic graphs (graphs in which every vertex has degree 3) are the critical case, since they are where the largest known ratios of cc(G)/mcc(G)/m occur. A useful technique there is to choose a 2-factor — a spanning subgraph that is a disjoint union of circuits, which every bridgeless cubic graph possesses — whose complementary perfect matching (a set of edges covering every vertex exactly once) is then covered by additional short cycles; the achievable length is governed by the number of short circuits, especially 5-circuits, that any 2-factor must contain. Successive refinements of this method lowered the cubic bound from 34/21⋅m≈1.619m34/21\cdot m\approx1.619m (Kaiser, Král, Lidický, Nejedlý, and Šámal, 2010) through 1.6m1.6m (Candráková and Lukoťka, 2016) to 212/135⋅m≈1.5703m212/135\cdot m\approx1.5703m (Lukoťka, 2020). For arbitrary bridgeless graphs the 5/3⋅m5/3\cdot m bound stood for forty years until Song and Zhu (2025) proved cc(G)<29/18⋅m+(1/18)n2cc(G)<29/18\cdot m+(1/18)n_2, where n2n_2 is the number of degree-2 vertices, yielding in particular cc(G)≤5/3⋅m−(1/42)log⁡mcc(G)\le 5/3\cdot m-(1/42)\log m and cc(G)<29/18⋅m≈1.6111mcc(G)<29/18\cdot m\approx1.6111m for graphs of minimum degree at least 3. On the lower-bound side, the ratio 7/57/5 is attained not only by the Petersen graph but by infinitely many cyclically 2- and 3-edge-connected cubic graphs (a graph is cyclically kk-edge-connected if no set of fewer than kk edges separates two disjoint cycles of the graph), while cyclically 4-edge-connected cubic graphs appear to stay near the natural barrier 4/34/3 (at each vertex of a cubic graph at least two cycle passages are needed, which forces the total length to be at least 4m/34m/3); Máčajová and Škoviera (2021) nevertheless constructed an infinite family of cyclically 4-edge-connected cubic graphs whose shortest cycle covers have length at least (4/3+1/69)m(4/3+1/69)m, disproving the conjecture that 4/3+o(m)4/3+o(m) suffices for that class. The problem is connected to flows on graphs: a nowhere-zero 5-flow is an assignment of nonzero weights from {1,…,4}\{1,\dots,4\} to the edges of an orientation of GG that is conserved at every vertex modulo 5, and Jamshy, Raspaud, and Tarsi (1987) showed that graphs with such a flow have cc(G)≤1.6mcc(G)\le 1.6m. The conjecture also implies the Cycle Double Cover Conjecture of Szekeres and Seymour — that every bridgeless graph has a collection of cycles covering every edge exactly twice (Jamshy and Tarsi, 1992) — which was resolved by a proof announced by OpenAI in July 2026. That resolution, however, only produces covers of total length exactly 2m2m and leaves the quantitative 7/57/5 question untouched. In this literature a cycle may also be taken to mean an even (Eulerian) subgraph, i.e. one in which every vertex has even degree; since such a subgraph decomposes into circuits of the same total length, the two conventions give the same value of cc(G)cc(G).

Problem Statement

Let GG be a finite bridgeless graph with m=∣E(G)∣m=|E(G)| edges, and let cc(G)cc(G) denote the minimum total length of a cycle cover of GG, i.e. a collection of cycles such that every edge of GG lies in at least one of them. The Short Cycle Cover Conjecture of Alon and Tarsi asserts that

cc(G)≤75mcc(G)\le\frac{7}{5}m

for every bridgeless graph GG. Determine whether this conjecture is true. An affirmative answer consists of a proof that every bridgeless graph with mm edges admits a cycle cover of total length at most 7m/57m/5; a negative answer consists of an explicit bridgeless graph GG with cc(G)>7∣E(G)∣/5cc(G)>7|E(G)|/5. The constant 7/57/5 is best possible, since the Petersen graph has m=15m=15 and cc=21=7/5⋅15cc=21=7/5\cdot 15, so no smaller constant can replace it. The conjecture is open both for arbitrary bridgeless graphs (best current bound 5/3⋅m−(1/42)log⁡m5/3\cdot m-(1/42)\log m) and for bridgeless cubic graphs specifically (best current bound 212/135⋅m≈1.5703m212/135\cdot m\approx1.5703m); an answer for all bridgeless graphs is sought, not merely for a restricted subclass.

References

  1. N. Alon and M. Tarsi, Covering Multigraphs by Simple Circuits, SIAM Journal on Algebraic Discrete Methods 6 (1985) 345–350. DOI: 10.1137/0606035, https://doi.org/10.1137/0606035
  2. J. C. Bermond, B. Jackson, and F. Jaeger, Shortest coverings of graphs with cycles, Journal of Combinatorial Theory, Series B 35 (1983) 297–308. DOI: 10.1016/0095-8956(83)90056-4, https://doi.org/10.1016/0095-8956(83)90056-4
  3. B. Candráková and R. Lukoťka, Short Cycle Covers on Cubic Graphs by Choosing a 2-Factor, SIAM Journal on Discrete Mathematics 30 (2016) 2086–2106. DOI: 10.1137/15M1045144; arXiv:1509.07430
  4. T. Kaiser, D. Král, B. Lidický, P. Nejedlý, and R. Šámal, Short Cycle Covers of Graphs with Minimum Degree Three, SIAM Journal on Discrete Mathematics 24 (2010) 330–355. DOI: 10.1137/080717468, https://doi.org/10.1137/080717468
  5. R. Lukoťka, Short Cycle Covers of Cubic Graphs and Intersecting 5-Circuits, SIAM Journal on Discrete Mathematics 34 (2020) 188–211. DOI: 10.1137/19M1241866, https://doi.org/10.1137/19M1241866
  6. E. Máčajová and M. Škoviera, Cubic Graphs with No Short Cycle Covers, SIAM Journal on Discrete Mathematics 35 (2021) 2223–2233. DOI: 10.1137/21M1399208, https://doi.org/10.1137/21M1399208
  7. D. Song and X. Zhu, Bound on Shortest Cycle Covers, Combinatorica 45 (2025). DOI: 10.1007/s00493-025-00191-x; arXiv:2412.20874, https://arxiv.org/abs/2412.20874
  8. J. Karabáš, E. Máčajová, R. Nedela, and M. Škoviera, Cubic graphs of colouring defect 3 and conjectures of Berge and Alon-Tarsi (2025). arXiv:2505.17569, https://arxiv.org/abs/2505.17569
  9. J. Karabáš and E. Máčajová, On 4-covers of cubic graphs with two adjacent odd circuits in a 2-factor (2026). arXiv:2605.09475, https://arxiv.org/abs/2605.09475
  10. Y. Luo, R.-X. Hao, R. Luo, and C.-Q. Zhang, A Note on Alon–Tarsi Shortest Cycle Cover Conjecture, Journal of Graph Theory 112 (2026) 172–177. DOI: 10.1002/jgt.70026, https://doi.org/10.1002/jgt.70026
  11. S. Liu, R.-X. Hao, R. Luo, and C.-Q. Zhang, Five-cycle double cover and shortest cycle cover, Journal of Graph Theory 108 (2024) 39–49. DOI: 10.1002/jgt.23164, https://doi.org/10.1002/jgt.23164
  12. OpenAI, A Proof of the Cycle Double Cover Conjecture (2026). https://cdn.openai.com/pdf/04d1d1e4-bc75-476a-97cf-49055cd98d31/cdc_proof.pdf
  13. S. Oum, A proof of the cycle double cover conjecture by OpenAI: An exposition (2026). arXiv:2607.16356, https://arxiv.org/abs/2607.16356
  14. J. Geelen, OpenAI's proof of the Cycle Double Cover Theorem (2026). arXiv:2607.15399, https://arxiv.org/abs/2607.15399
  15. R. Hušek and R. Šámal, Exponentially Many Circuit Double Covers (2026). arXiv:2607.24724, https://arxiv.org/abs/2607.24724
  16. U. Jamshy, A. Raspaud, and M. Tarsi, Short circuit covers for regular matroids with a nowhere zero 5-flow, Journal of Combinatorial Theory, Series B 43 (1987) 354–357. DOI: 10.1016/0095-8956(87)90011-6, https://doi.org/10.1016/0095-8956(87)90011-6
  17. U. Jamshy and M. Tarsi, Short cycle covers and the cycle double cover conjecture, Journal of Combinatorial Theory, Series B 56 (1992) 197–204. DOI: 10.1016/0095-8956(92)90018-S, https://doi.org/10.1016/0095-8956(92)90018-S
  18. E. Máčajová, A. Raspaud, M. Tarsi, and X. Zhu, Short cycle covers of graphs and nowhere-zero flows, Journal of Graph Theory 68 (2011) 340–348. DOI: 10.1002/jgt.20563, https://doi.org/10.1002/jgt.20563