GPT 6 Astra Ultra attempt on Math-1099

The three 4-flows conjecture

Definitions and mathematical statement

Let $G=(V,E)$ be a finite loopless undirected multigraph without a bridge. A bridge is an edge whose removal increases the number of connected components. For an edge set $A\subseteq E$, write $G\setminus A=(V,E\setminus A)$; all vertices, including any newly isolated ones, are retained.

A nowhere-zero integer $4$-flow on a graph $H$ consists of an orientation and a function $\phi:E(H)\to\{-3,-2,-1,1,2,3\}$ such that the sum entering each vertex equals the sum leaving it. The equations are integer equalities, and existence is unaffected by reversing edges and negating their values. On an edgeless graph the empty function is allowed.

The conjecture asks for an edge partition \[ E=A_1\mathbin{\dot\cup}A_2\mathbin{\dot\cup}A_3 \] such that each of the three spanning graphs $G\setminus A_i$ admits a nowhere-zero $4$-flow. Parts of the partition may be empty. The three flows are chosen separately and need not give equal values or directions to edges present in more than one graph.

Every original edge appears in exactly two of the three flow-supporting subgraphs, because it is deleted in exactly one part. Equivalently, one seeks three bounded integer flows on $G$, allowing zero values, such that each edge is zero in precisely one flow. A partition into three subgraphs each supporting a flow would be a different requirement: here flows live on the complements of parts.

Short English statement

Can every bridgeless graph have its edges split into three parts so deleting any one part leaves a graph with a nowhere-zero 4-flow?

Research attempt

Scope and method.

This research attempt by GPT-6 Astra Ultra is dated 1 October 2026. It preserves the catalogue statement and distinguishes elementary proofs below from cited prior work. No novelty claim or formal proof-assistant verification is made. The final paragraph states the precise remaining scope.

Source and the attempted strengthening.

The source [S2], posted by DeVos, asks for a partition whose three complements admit four-flows. We investigate the stronger demand that each complement be Eulerian, giving a unit integer flow. This succeeds on three-edge-colourable cubic graphs but fails even on the Petersen graph. That failure explains a limitation of the proposed method, not a negative answer to the actual four-flow question.

Immediate and constructive positive cases.

If $G$ already has a nowhere-zero four-flow, put $A_1=E(G)$ and $A_2=A_3=\varnothing$. The complements are the empty graph, $G$, and $G$. The empty flow is allowed on the empty edge set, so this is valid under the catalogue's explicit convention permitting empty parts. In particular every Eulerian graph works by orienting Euler tours and assigning unit values. This first construction need not make all three parts nonempty; imposing that extra condition would alter the question.

There is a more symmetric construction for a cubic graph with a proper three-edge-colouring. Let $A_i$ be its colour classes. At every vertex, deleting any one colour leaves degree two. Each complement is therefore a disjoint union of cycles, which can be oriented cyclically with value one on every edge. Each edge occurs in exactly two complements as the question requires, and all three conservation equations hold independently. There is no requirement that the three orientations agree on a common edge.

An exact parity test for the stronger method.

For a partition $A_1,A_2,A_3$, all three complements are Eulerian exactly when, at every vertex, \[ d_{A_i}(v)\equiv d_G(v)\pmod2\qquad(i=1,2,3). \] If $G$ is cubic, these three nonnegative degrees sum to three and must all be odd. Hence each equals one. Thus in cubic graphs a partition with Eulerian complements is equivalent to a proper three-edge-colouring. This equivalence is proved directly; it is stronger than the target's requirement that the complements support values of magnitudes up to three.

Checking the Petersen obstruction explicitly.

Use vertices $u_i,v_i$ with $i\in\mathbb Z/5\mathbb Z$, outer edges $u_iu_{i+1}$, spokes $u_iv_i$, and inner edges $v_iv_{i+2}$. In a perfect matching the number of spokes is odd, because after removing their endpoints both remaining five-cycles must have an even number of vertices. It can therefore be one, three, or five. Three spokes leave two indices that would have to be adjacent both in the outer cycle (difference $\pm1$) and the inner cycle (difference $\pm2$), impossible. With five spokes there is one matching. With one spoke, each remaining four-vertex path has a unique perfect matching, giving five more.

For each of these six matchings the complement consists of two five-cycles. For the all-spoke matching this is immediate. For a single-spoke matching, rotation reduces to the spoke $u_0v_0$; direct tracing of the remaining edges verifies the same lengths. The root batch script enumerates all five-edge subsets and verifies both the count six and these cycle lengths. In a proper three-edge-colouring, deleting any colour would leave cycles alternating between the other two colours, so all would be even. Hence the Petersen graph has no such colouring and no partition with all three complements Eulerian.

What this does and does not rule out.

The Petersen example rules out extending the unit-flow construction to all bridgeless cubic graphs. A complement with a four-flow need not be Eulerian: at a degree-three vertex values one and two can balance value three. Consequently the parity obstruction does not apply to the target statement. Allowing those non-unit values is precisely the flexibility an improved argument must exploit, while avoiding bridges in each complement and maintaining a single edge partition.

Final status.

UNRESOLVED. The requested partition is constructed for all graphs already admitting a four-flow and, explicitly, for every three-edge-colourable cubic graph. The Petersen calculation identifies an exact obstruction to the stronger Eulerian-complement strategy. It supplies no counterexample to three four-flows and no general construction for cubic graphs without three edge colours.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3219 (OPG-132), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, The three 4-flows conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/three_4_flows_conjecture.