Small Oriented Cycle Double Cover Conjecture: does every simple 2-connected graph other than $K_4$ and $K_6$ admit an oriented cycle double cover with at most $n-1$ directed cycles?

The Small Oriented Cycle Double Cover (SOCDC) conjecture of Bagheri Gh. and Omoomi asserts that every simple 2-connected graph on $n$ vertices, with exactly the two exceptions $K_4$ and $K_6$, has an oriented cycle double cover (OCDC) — a collection of directed cycles in the symmetric orientation of the graph that covers every directed arc exactly once — consisting of at most $n-1$ cycles. The conjecture simultaneously strengthens the classical Cycle Double Cover (CDC) conjecture, proved only in July 2026 via an announcement by OpenAI, the still-open oriented CDC conjecture, and Bondy's still-open small CDC conjecture; hence it is strictly harder than any of these. Known partial results consist of necessary conditions on a hypothetical minimal counterexample (minimum degree at least 3, 3-connectivity, 3-edge-connectivity, and no non-trivial 3-edge-cut) and a list of graph classes admitting an SOCDC (complete graphs other than $K_4$, $K_6$; even graphs of maximum degree 4; planar, projective, and $K_6^-$-minor-free even graphs; line graphs of even or odd graphs; graphs whose girth exceeds their average degree). The conjecture remains open.

Background

A cycle double cover (CDC) of a graph $G$ is a collection of cycles such that every edge of $G$ lies in exactly two of them; a bridge is an edge whose deletion disconnects the graph, and only bridgeless graphs can have a CDC. The CDC conjecture, formulated by Szekeres and Seymour around 1979, states that every bridgeless graph has a CDC; in July 2026 OpenAI announced a proof, with independent expositions by Geelen and by Oum confirming that the method — linear algebra converting a nowhere-zero $\mathbb{F}_2^3$-flow (an assignment to each edge of a non-zero flow value from $\mathbb{F}_2^3$, the eight-element three-dimensional vector space over the two-element field, such that the flow values of the edges incident with each vertex sum to zero) into an edge-bicolouring (an assignment of a pair of colours to each edge such that each colour occurs an even number of times at each vertex, which is equivalent to a CDC since each colour class decomposes into edge-disjoint cycles) — settles only the unoriented, unbounded statement. Two long-standing strengthenings remain open: Bondy's small cycle double cover (SCDC) conjecture, that every simple 2-edge-connected graph on $n$ vertices has a CDC with at most $n-1$ cycles, and the oriented CDC (OCDC) conjecture, that every bridgeless graph has an oriented CDC. Here the symmetric orientation $G_s$ of $G$ replaces each edge by a pair of opposite arcs, and an OCDC is a collection of directed cycles of $G_s$ covering each arc exactly once, i.e. each edge is traversed once in each direction; this is strictly stronger in appearance than a CDC (for example, the Petersen graph has a CDC that cannot be oriented so as to form an OCDC, as the source paper notes). Bagheri Gh. and Omoomi combined the two strengthenings: an SOCDC of a graph on $n$ vertices is an OCDC with at most $n-1$ directed cycles. The bound cannot be improved: every OCDC of $K_4$ has exactly 4 cycles, and $K_6$ has an OCDC of exactly 6 cycles but no OCDC with at most 5 cycles, so these two graphs are genuine exceptions (by a theorem of Maxová and Nešetřil relating oriented perfect path double covers — OPPDCs, families of directed paths covering each arc once and using each vertex once as a path start and once as a path end — the absence of small covers follows from the facts that $K_3$ and $K_5$ have no OPPDC, since $G$ has an OPPDC if and only if $G \vee K_1$, the join with a new universal vertex, has an SOCDC). Their SOCDC conjecture states that every simple 2-connected graph except $K_4$ and $K_6$ admits an SOCDC. Known supporting evidence: every $K_{2n}$ with $n \geq 4$ and every $K_{2n+1}$ has an SOCDC; graphs whose blocks have SOCDCs glue together; and, because doubling the cycles of a decomposition of an even graph (all degrees even) into $\lfloor (n-1)/2 \rfloor$ cycles — Hajós' cycle conjecture, itself still open in general and verified only up to 12 vertices — yields an SOCDC, all even graph classes where Hajós' conjecture is known to hold inherit an SOCDC (maximum degree 4, planar by Seyffarth, projective-planar and $K_6^-$-minor-free by Fan and Xu, even line graphs by Klimmek). For a refutation one knows that a minimal counterexample must have minimum degree at least 3, be 3-connected, 3-edge-connected, and have no non-trivial 3-edge-cut. A positive resolution of the SOCDC conjecture would imply the OCDC conjecture for simple graphs (via its blocks) and Bondy's SCDC conjecture for simple 2-connected graphs — both open even after the 2026 CDC proof, as Oum's exposition explicitly notes.

Problem Statement

Prove or refute the Small Oriented Cycle Double Cover (SOCDC) conjecture of Bagheri Gh. and Omoomi: every simple 2-connected graph $G$ on $n$ vertices, other than the complete graphs $K_4$ and $K_6$, admits an oriented cycle double cover with at most $n-1$ directed cycles — that is, a collection $\mathcal{C}$ of at most $n-1$ directed cycles (simple closed directed walks of length at least 3) in the symmetric orientation $G_s$ of $G$ (obtained by replacing each edge of $G$ with two opposite arcs) such that every arc of $G_s$ lies in exactly one cycle of $\mathcal{C}$, so each edge of $G$ is traversed exactly once in each direction. A refutation consists of a simple 2-connected graph, not isomorphic to $K_4$ or $K_6$, for which every oriented cycle double cover requires at least $n$ directed cycles; the two exceptions are genuine, since every OCDC of $K_4$ has exactly 4 cycles, and $K_6$ admits an OCDC of exactly 6 cycles but has no OCDC with at most 5 cycles. The problem must be answered at this full generality: no restriction to special graph classes, degree bounds, embeddings, or answer forms narrows it.

References

1. Behrooz Bagheri Gh. and Behnaz Omoomi, Small oriented cycle double cover of graphs, Bulletin of the Malaysian Mathematical Sciences Society 39(1):219–225 (published online 2015), DOI 10.1007/s40840-015-0169-2, arXiv:1207.5122, https://arxiv.org/abs/1207.5122 (source paper)
2. Behrooz Bagheri Gh. and Behnaz Omoomi, On the oriented perfect path double cover conjecture, Bulletin of the Iranian Mathematical Society 41(1):189–200 (2015), arXiv:1207.1961, https://arxiv.org/abs/1207.1961
3. Jana Maxová and Jaroslav Nešetřil, On oriented path double covers, Discrete Mathematics 233(1-3):371–380 (2001), DOI 10.1016/S0012-365X(00)00253-3, https://doi.org/10.1016/S0012-365X(00)00253-3
4. Jana Maxová and Jaroslav Nešetřil, On covers of graphs, Discrete Mathematics 276(1-3):287–294 (2004), DOI 10.1016/S0012-365X(03)00314-5, https://doi.org/10.1016/S0012-365X(03)00314-5
5. J. Adrian Bondy, Small cycle double covers of graphs, in: G. Hahn, G. Sabidussi, R. Woodrow (eds.), Cycles and Rays, NATO ASI Series C, Kluwer, Dordrecht (1990), pp. 21–40, DOI 10.1007/978-94-009-0517-7_4, https://doi.org/10.1007/978-94-009-0517-7_4
6. Genghua Fan and Baogang Xu, Hajós' conjecture and projective graphs, Discrete Mathematics 252(1-3):91–101 (2002), DOI 10.1016/S0012-365X(01)00290-4, https://doi.org/10.1016/S0012-365X(01)00290-4
7. Karen Seyffarth, Hajós' conjecture and small cycle double covers of planar graphs, Discrete Mathematics 101(1-3):291–306 (1992), DOI 10.1016/0012-365X(92)90610-R, https://doi.org/10.1016/0012-365X(92)90610-R
8. Irene Heinrich, Marco V. Natale, and Manuel Streicher, Hajós' cycle conjecture for small graphs, arXiv:1705.08724 (2017), https://arxiv.org/abs/1705.08724
9. Sang-il Oum, A proof of the cycle double cover conjecture by OpenAI: An exposition, arXiv:2607.16356v3 (2026), https://arxiv.org/abs/2607.16356
10. Jim Geelen, OpenAI's proof of the Cycle Double Cover Theorem, arXiv:2607.15399 (2026), https://arxiv.org/abs/2607.15399
11. Radek Hušek and Robert Šámal, Exponentially Many Circuit Double Covers, arXiv:2607.24724 (2026), https://arxiv.org/abs/2607.24724
12. Jorik Jooken, Ben Seamone, and Carol T. Zamfirescu, Counting Small Cycle Double Covers, arXiv:2506.10604 (2025), https://arxiv.org/abs/2506.10604
13. Nikolay Ulyanov, Graph Puzzles I.1: Oriented Berge-Fulkerson Conjecture, arXiv:2501.05348 (2025), https://arxiv.org/abs/2501.05348
14. M. N. Ellingham and Xiaoya Zha, Orientable embeddings and orientable cycle double covers of projective-planar graphs, European Journal of Combinatorics 32:495–509 (2011), DOI 10.1016/j.ejc.2011.01.001, https://doi.org/10.1016/j.ejc.2011.01.001