gpt 6 astra ultra attempt on Math-1073

(m,n)-cycle covers

Definitions and mathematical statement

Let $G=(V,E)$ be a finite undirected loopless multigraph. A binary cycle is an edge set $C\subseteq E$ such that every vertex of the spanning subgraph $(V,C)$ has even degree. The empty set is allowed. A binary cycle may be disconnected and may have vertices of degree greater than two; equivalently, its edges can be partitioned into ordinary circuits.

For positive integers $m,n$, an $(m,n)$-cycle cover is a list $C_1,\ldots,C_m$ of binary cycles such that \[ \sum_{i=1}^m\mathbf1_{\{e\in C_i\}}=n \qquad\text{for every }e\in E. \] The list may contain repeated entries, and empty entries allow a cover with fewer than $m$ nonempty members to be padded. Membership of one edge in one binary cycle counts once.

The conjecture is that every bridgeless $G$ admits a $(5,2)$-cycle cover, where bridgeless means that deleting any single edge does not increase the number of connected components. Thus five even-degree edge sets should together cover each original edge exactly twice.

The number five bounds these binary cycles, not the number of connected circuits arising after they are decomposed. In a cubic graph every nonzero degree inside a binary cycle is two, so each of the five members is a vertex-disjoint union of circuits. No connectivity of $G$ or of the covering members is required; components can be handled with the same five indices.

Short English statement

Can the edges of every bridgeless graph be covered exactly twice by five even-degree subgraphs?

Research attempt: compressing four binary cycles and the five-colour barrier

Scope and literature check.

GPT-6 Astra Ultra, 1 October 2026. Here a cycle means an even-degree edge set, not necessarily one circuit. Oum's 2026 exposition [S3] presents the announced ordinary cycle double cover proof and explicitly lists the five-cycle double cover conjecture separately. Thus a cover with an unrestricted number of circuits does not already settle the canonical five-member target. Liu, Hao, Luo and Zhang [S4] study five-cycle covers using flows and reductions. The work below supplies a self-contained compression argument, identifies its exact limit, and checks a small obstruction to using fewer members.

1. Three members and a two-coordinate flow.

Suppose $A,B,C$ are binary cycles covering each edge twice. The membership sum is zero modulo two, so $C=A\mathbin{\triangle}B$. No edge is absent from both $A$ and $B$, since then it could occur only in $C$, contrary to multiplicity two. Consequently the labels \[ f(e)=(\mathbf1_A(e),\mathbf1_B(e))\in\mathbb F_2^2 \] are nonzero, and their sum at every vertex is zero because $A$ and $B$ are even subgraphs. Conversely, any such nonzero labelling with zero vertex sums gives the binary cycles $A,B,A\triangle B$, covering each edge twice: a nonzero two-bit vector has total membership two in its first coordinate, second coordinate, and their sum.

2. Four members can always be compressed to three.

Let $C_1,\ldots,C_4$ be a double cover. Assign distinct labels $t_1=00,t_2=01,t_3=10,t_4=11$ in $\mathbb F_2^2$. Each edge belongs to exactly two distinct indices $i,j$, even if some members of the list happen to be equal as sets. Label that edge $f(e)=t_i+t_j$. It is nonzero. At each vertex $v$, \[ \sum_{e\ni v}f(e)=\sum_{i=1}^4 t_i\deg_{C_i}(v)=0, \] since each degree on the right is even. The preceding construction therefore produces a three-member double cover. Padding with an empty member proves the converse. Hence $(3,2)$ and $(4,2)$ existence are equivalent for every loopless multigraph.

For cubic graphs the three nonzero labels on incident edges must be pairwise distinct: if two were equal, the zero-sum condition would force the third to be zero. Thus a three-member double cover gives a proper three-edge-colouring. Conversely, the three unions of pairs of colour classes form a double cover. This establishes the equivalence without confusing connected circuits with binary cycles.

3. Why the same compression does not handle five.

An assignment of fixed labels $t_1,\ldots,t_5\in\mathbb F_2^2$ cannot make $t_i+t_j$ nonzero for all distinct pairs: there are only four labels, so some pair coincides. A particular cover might avoid that pair, but the five-member hypothesis alone gives no such restriction. This disproves only the universal fixed-label compression scheme. It does not disprove a five-member double cover or rule out a construction using a different algebraic structure.

A concrete check is provided by the Petersen graph, with outer cycle $0,1,2,3,4,0$, spokes $i(i+5)$, and inner edges $(i+5)(5+(i+2\bmod5))$. Exhaustively checking its $\binom{15}{5}$ five-edge subsets finds exactly six perfect matchings; every complement consists of two five-cycles. A proper three-edge-colouring would make each colour class a perfect matching whose complement is a union of even alternating circuits. Hence this graph has no three- or four-member double cover. The check script [S5] reproduces that entire finite argument, including the component lengths, and verifies an explicit five-member double cover. Thus the obstruction does not extend to the conjectured number five.

Verification and first remaining gap.

All parity identities above hold for parallel edges counted separately. The finite Petersen enumeration certifies one graph only; it is not evidence for a uniform bound over arbitrary order. The unresolved task is producing five even edge sets on every bridgeless graph, or an appropriate pair-label system satisfying every vertex constraint. Neither the ordinary double-cover theorem nor the two-coordinate compression provides that construction.

Final status

UNRESOLVED. The equivalence of three- and four-member covers is proved, the fixed-label five-member shortcut is obstructed, and the Petersen boundary example is verified. The general five-member assertion is not established. Completion estimate: no defensible global percentage.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3163 (OPG-139), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, (m,n)-cycle covers. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/m_n_cycle_covers.
• S3 S.-i. Oum, A proof of the cycle double cover conjecture by OpenAI: An exposition, arXiv:2607.16356v3 $2026$, Section 9.2. Checked 1 October 2026. https://arxiv.org/abs/2607.16356.
• S4 S. Liu, R.-X. Hao, R. Luo and C.-Q. Zhang, 5-Cycle Double Covers, 4-Flows, and Catlin Reduction, SIAM Journal on Discrete Mathematics $2023$. Checked 1 October 2026. https://doi.org/10.1137/22M1472425.
• S5 GPT-6 Astra Ultra, exhaustive Petersen matching check and five-cover certificate, 1 October 2026: scripts/check_attempt_batch02_connectivity_2026_10_01.py in this repository; run with Python 3.