Non-separating cycles whose contractions carry nowhere-zero 4-flows in cyclically 4-edge-connected cubic graphs (Hoffmann-Ostenhof-Zhang-Zhang Conjecture 5.2 and Problem 5.1)

Hoffmann-Ostenhof, Zhang and Zhang (European Journal of Combinatorics 81, 2019) proved that a 2-edge-connected graph containing a non-separating cycle $C$ whose contraction $G/E(C)$ admits a nowhere-zero 4-flow has a 5-cycle double cover containing $C$ , and left open two linked questions about the reach of this criterion. Conjecture 5.2 asserts that every cyclically 4-edge-connected cubic graph contains a non-separating cycle whose contraction admits a nowhere-zero 4-flow; by the paper's own argument this would imply the 5-cycle double cover conjecture. Problem 5.1 asks whether some snark with a decomposition into a spanning tree and a cycle $C$ has a contraction $G/E(C)$ admitting no nowhere-zero 4-flow. Both formulations appear in Section 5 of the paper, and both remain open; OpenAI's announced July 2026 proof of the cycle double cover conjecture yields 8-cycle double covers but leaves the 5-cycle double cover conjecture open.

Background

A cycle double cover (CDC) of a graph $G$ is a collection of cycles of $G$ such that every edge lies in exactly two members of the collection; following the source paper's terminology, a cycle is any subgraph in which every vertex has even degree (so a 2-regular subgraph of a cubic graph is a cycle, possibly disconnected, whose connected components are circuits), and a $k$ -CDC is a CDC with at most $k$ cycles (the source paper defines a $k$ -CDC as a set of exactly $k$ cycles; the two conventions do not affect the open questions below, neither of which concerns CDC counts). The Cycle Double Cover Conjecture (CDCC), a famous problem from the late 1970s, asserts that every bridgeless graph has a CDC, and its strengthening, the 5-cycle double cover (5-CDC) conjecture, asks for a CDC with at most five cycles. Both are customarily reduced to snarks: cubic graphs (all vertices of degree three) that are cyclically 4-edge-connected (no edge cut of at most three edges separates two subgraphs that each contain a circuit), have girth at least five, and admit no proper 3-edge-coloring. A nowhere-zero 4-flow on an oriented graph is an assignment of nonzero values to the edges, from $\mathbb{Z}_4$ or $\mathbb{Z}_2^2$ (equivalently, by a classical theorem of Tutte, nonzero integers of absolute value at most three), such that flow is conserved at every vertex; for cubic graphs, admitting a nowhere-zero 4-flow is equivalent to being 3-edge-colorable, so snarks are precisely the girth- and connectivity-restricted cubic graphs that carry no nowhere-zero 4-flow.

A cycle $C$ of a connected graph $G$ is called non-separating if $G-E(C)$ is connected, and $G/E(C)$ denotes the graph obtained by contracting every edge of $C$ . The source paper's central tool (its Theorem 3.1) states that if $G$ is 2-edge-connected and contains a non-separating cycle $C$ such that $G/E(C)$ admits a nowhere-zero 4-flow, then $G$ has a 5-CDC containing $C$ . This criterion powers the paper's progress on a 2017 conjecture of Hoffmann-Ostenhof (recorded on the Open Problem Garden): every non-separating cycle of a 2-edge-connected cubic graph is contained in some CDC of that graph, equivalently every 2-edge-connected cubic graph with a decomposition into a spanning tree $T$ and a 2-regular subgraph $C$ has a CDC containing $C$ (in such a decomposition $C$ is automatically non-separating because $G-E(C)=T$ ). The paper proves this when $C$ has at most three circuits (its Theorem 3.6: a 5-CDC containing $C$ , or a 6-CDC when $G$ can be contracted to the Petersen graph, the standard 10-vertex cubic graph of girth five, which is itself the smallest snark), the proof resting on Theorem 3.1 together with a classical contraction lemma (Lemma 2.4 of the paper): contracting a circuit of length at most four preserves the existence of nowhere-zero 4-flows.

The reach of this contraction-flow criterion is not understood. The paper constructs a snark $Q^*$ , from a known example of a graph without a nowhere-zero 4-flow, containing a maximal non-separating cycle $C^*$ (not contained in any larger non-separating cycle) such that $Q^*/E(C^*)$ has no nowhere-zero 4-flow; thus Theorem 3.1 cannot always be applied, even on snarks, even though $C^*$ happens to lie in some CDC of $Q^*$ . The paper draws two open questions from this observation, which are the subject of this problem record. The 2026 landscape sharpens their interest: in July 2026 OpenAI announced a proof of the CDCC itself (a labeling argument over $\mathbb{F}_2^3$ , with independent expositions by Geelen and by Oum), and the method yields a CDC with at most eight cycles for every bridgeless graph, but the 5-CDC conjecture remains open. Since the source paper argues that Conjecture 5.2 would imply the 5-CDC conjecture (via Theorem 3.1 and the standard reduction to snarks), the conjecture remains a live route to the strongest still-open cycle-cover question.

Problem Statement

Determine how widely the contraction-flow criterion of Hoffmann-Ostenhof-Zhang-Zhang is available on cyclically 4-edge-connected cubic graphs, by answering the two linked questions their paper left open.

(1) Conjecture 5.2 (primary). Prove or disprove: every cyclically 4-edge-connected cubic graph $G$ contains a non-separating cycle $C$ , i.e. one with $G-E(C)$ connected, such that the contraction $G/E(C)$ admits a nowhere-zero 4-flow (over $\mathbb{Z}_4$ or $\mathbb{Z}_2^2$ , equivalent by Tutte's theorem to an integer 4-flow with all values nonzero). For cubic graphs that already carry a nowhere-zero 4-flow (equivalently, 3-edge-colorable ones), the flow condition on $G/E(C)$ is automatic for any non-separating cycle, since nowhere-zero 4-flow existence passes to contractions; the substantive case is snarks, which have no nowhere-zero 4-flow themselves, so the claim is that contracting one suitable non-separating cycle always destroys the obstruction. By the source paper's Theorem 3.1 and the standard reduction to snarks, a proof would establish the 5-cycle double cover conjecture for all bridgeless graphs.

(2) Problem 5.1 (companion). Does there exist a snark $G$ (cubic, bridgeless, girth at least five, cyclically 4-edge-connected, not 3-edge-colorable) with a decomposition of its edge set into a spanning tree $T$ and a 2-regular subgraph $C$ (a cycle in the paper's terminology, possibly with several circuits) such that $G/E(C)$ does not admit a nowhere-zero 4-flow? An affirmative answer exhibits a snark in which the criterion fails even for cycles arising from tree decompositions, showing that Theorem 3.1 alone cannot prove the source's decomposition conjecture restricted to snarks; a negative answer shows the criterion always applies in that setting. The known snark $Q^*$ of the source paper does not answer this, because its exceptional cycle $C^*$ does not come from a tree decomposition ( $Q^*-E(C^*)$ is connected but not a tree).

The common scientific objective is the availability of non-separating cycles with contractible nowhere-zero 4-flows, the route by which the source paper derives 5-cycle double covers; note that a single finite counterexample to (1) that is a snark and admits a tree-plus-cycle decomposition would answer (2) affirmatively at the same time.

References

Arthur Hoffmann-Ostenhof, Cun-Quan Zhang, Zhang Zhang, "Cycle double covers and non-separating cycles", European Journal of Combinatorics 81 (2019) 276-284. DOI: 10.1016/j.ejc.2019.06.006; arXiv:1711.10614, https://arxiv.org/abs/1711.10614
Xiaoyu Li, Rong-Xia Hao, Rong Luo, Cun-Quan Zhang, "Non-separating cycles and 5-cycle double covers", Discrete Mathematics 348 (2025) 114515. DOI: 10.1016/j.disc.2025.114515, https://doi.org/10.1016/j.disc.2025.114515
Arthur Hoffmann-Ostenhof, Thomas Jatschka, "Snarks with Special Spanning Trees", Graphs and Combinatorics 35 (2019) 207-219. DOI: 10.1007/s00373-018-1973-x; arXiv:1706.05595, https://arxiv.org/abs/1706.05595
OpenAI, "A proof of the cycle double cover conjecture", technical note, 2026, https://cdn.openai.com/pdf/04d1d1e4-bc75-476a-97cf-49055cd98d31/cdc_proof.pdf
Sang-il Oum, "A proof of the cycle double cover conjecture by OpenAI: An exposition", arXiv:2607.16356 (2026), https://arxiv.org/abs/2607.16356
Jim Geelen, "OpenAI's proof of the Cycle Double Cover Theorem", arXiv:2607.15399 (2026), https://arxiv.org/abs/2607.15399
Radek Hušek, Robert Šámal, "Exponentially Many Circuit Double Covers", arXiv:2607.24724 (2026), https://arxiv.org/abs/2607.24724
Edita Máčajová, Martin Škoviera, "Superposition of snarks revisited", European Journal of Combinatorics 91 (2021) 103220. DOI: 10.1016/j.ejc.2020.103220, https://doi.org/10.1016/j.ejc.2020.103220
Siyan Liu, Rong-Xia Hao, Cun-Quan Zhang, "Berge-Fulkerson coloring for some families of superposition snarks", European Journal of Combinatorics 96 (2021) 103344. DOI: 10.1016/j.ejc.2021.103344, https://doi.org/10.1016/j.ejc.2021.103344
Davide Mattiolo, "On removable edge subsets in graphs with a nowhere-zero 4-flow", arXiv:2511.01556 (2025), https://arxiv.org/abs/2511.01556
Xiaoyu Li, Rong-Xia Hao, Yilun Luo, Siyan Liu, "Ban-Linial's Conjecture and Halin Snarks", Journal of Graph Theory (2026). DOI: 10.1002/jgt.70080, https://doi.org/10.1002/jgt.70080
Arthur Hoffmann-Ostenhof, "Cycle Double Covers Containing Predefined 2-Regular Subgraphs", Open Problem Garden entry (2017), http://www.openproblemgarden.org/op/cycle_double_covers_containing_predefined_2_regular_subgraphs