Cycle Double Covers Containing Predefined 2-Regular Subgraphs

Cycle Double Covers Containing Predefined 2-Regular Subgraphs

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple cubic graph that is $2$-connected: it has at least three vertices and remains connected after deletion of any one vertex. A circuit means a connected $2$-regular subgraph, or equivalently a simple cycle. Let $S$ be a $2$-regular subgraph of $G$, possibly with several components, and suppose that the spanning graph $(V,E\setminus E(S))$ is connected. Deleting the edges of $S$ retains all vertices of $G$.

A cycle double cover of $G$ is a finite list $\mathcal C$ of circuits such that, counting appearances in the list, \[ \left|\{C\in\mathcal C:e\in E(C)\}\right|=2 \qquad(e\in E). \] Repetitions are permitted by the general cover convention. To say that the cover contains $S$ means that every circuit component of $S$ occurs as an entire member of $\mathcal C$. Merely covering the edges of $S$ within other circuits does not meet this requirement.

The conjecture asserts that such a cover containing $S$ exists for every pair $(G,S)$ satisfying the hypotheses. There is no prescribed bound on the number of covering circuits and no requirement that they be disjoint. The connectivity assumption is imposed on the edge complement of the specified subgraph, and $S$ is not assumed to be spanning. These distinctions determine which prescribed cycle families the extension statement addresses.

Short English statement

Can every prescribed union of disjoint cycles whose removal leaves a cubic graph connected be retained inside a cycle double cover?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 1 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Literature and conventions.

Hoffmann-Ostenhof, Zhang and Zhang [R1] study prescribed $2$-regular subgraphs and prove sufficient conditions, including particular tree-and-cycle decompositions. The target here retains every component of $S$ as an entire circuit. We prove two restricted extension mechanisms and explain why parity alone cannot replace that requirement. In this text a circuit is simple and connected, exactly as in the retained statement.

A local necessary transition rule.

At a vertex of a cubic graph, name the incident edges $a,b,c$. Every circuit passing through the vertex uses exactly one pair of these edges. Let $x_{ab},x_{ac},x_{bc}$ count the occurrences of the three pairs in a cycle double cover. Covering every edge twice requires \[ x_{ab}+x_{ac}=2,\quad x_{ab}+x_{bc}=2,\quad x_{ac}+x_{bc}=2. \] The unique solution is $x_{ab}=x_{ac}=x_{bc}=1$. Thus each local pair must be used exactly once. A specified circuit fixes one of these transitions at every vertex it visits; a proof must complete the other transitions coherently around whole circuits. Counting even edge multiplicities alone omits this compatibility.

A full extension in a compatible edge-colouring subcase.

Suppose $G$ has a proper edge-colouring by $1,2,3$, and every component of $S$ is bichromatic in this colouring. For each pair $\{i,j\}$ take the subgraph consisting of edges of those two colours. Every vertex has one edge of each colour, so this is a spanning $2$-regular subgraph; split it into its simple circuit components. Collect the components from all three colour pairs. An edge of colour $i$ appears in exactly the two pairs containing $i$, so the resulting list is a cycle double cover.

If a component $K$ of $S$ uses colours $i,j$, then at every vertex of $K$ its two edges already exhaust the two edges in that colour-pair subgraph. It follows that $K$ is an entire component of that subgraph and hence occurs in the cover as required. Different components of $S$ may use different pairs. This argument does not need the edge-complement connectivity hypothesis, but it does need the extra compatible-colouring hypothesis.

A separate planar subcase.

Suppose a $2$-connected plane embedding of $G$ is given and every component of $S$ is the boundary of a face. In a $2$-connected plane graph each facial boundary is a simple circuit: a repeated boundary vertex would separate the portions encountered between two visits and be a cut vertex. Every edge has two sides, and the facial boundary circuits, including that of the unbounded face, therefore cover every edge exactly twice. They provide the desired cover containing $S$.

These two mechanisms are not interchangeable. In $K_4$, a triangle $S$ has connected edge complement (a three-edge star). The four triangles are a double cover and one may embed any chosen triangle as a face. But a triangle cannot be bichromatic in a proper edge-colouring: a two-coloured circuit must alternate colours and therefore have even length. The first mechanism misses this valid instance while the facial construction handles it.

A tempting Eulerian shortcut and its precise defect.

Replace each edge of $G$ by two parallel copies and remove one copy of each edge in $S$. The remaining multigraph has degree four at vertices of $S$ and degree six elsewhere, so it decomposes into circuits in the multigraph sense. Adding back $S$ then has the correct edge multiplicities. However, those multigraph circuits may be two-edge circuits formed by the parallel copies of a single original edge. Their projection to $G$ is not a simple circuit. Choosing such pairs for all doubled edges is precisely why even degree by itself gives no cycle double cover of an arbitrary bridgeless graph. A proof must exclude these projected backtracks and preserve the prescribed circuits simultaneously.

Verification and first remaining gap.

The edge-colouring proof tracks individual circuit components, not just the unions of two colour classes. The plane argument requires a compatible embedding; connectivity of $G-E(S)$ does not itself provide one or make $G$ planar. The local transition equations are necessary but contain no global assurance of simple projected circuits. UNRESOLVED: the remaining step is a general extension construction from the stated connectivity hypothesis alone, without either additional colouring or embedding.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3138 (OPG-60029), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Cycle Double Covers Containing Predefined 2-Regular Subgraphs. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/cycle_double_covers_containing_predefined_2_regular_subgraphs.

• R1 Arthur Hoffmann-Ostenhof, Cun-Quan Zhang and Zhang Zhang, Cycle double covers and non-separating cycles, European Journal of Combinatorics 81 $2019$, 276--284; primary preprint. https://arxiv.org/abs/1711.10614.