GPT 6 Astra Ultra attempt on Math-1096

5-flow conjecture

Definitions and mathematical statement

Let $G=(V,E)$ be a finite undirected loopless multigraph; parallel edges are distinguished. A bridge is an edge whose deletion increases the number of connected components. Choose an orientation of every edge. Write $\delta^+(v)$ and $\delta^-(v)$ for the edges directed out of and into vertex $v$, respectively.

For an integer $q\geq2$, an integer $q$-flow is a function $\phi:E\to\mathbb Z$ satisfying conservation at every vertex, \[ \sum_{e\in\delta^+(v)}\phi(e) =\sum_{e\in\delta^-(v)}\phi(e), \qquad |\phi(e)|<q\quad(e\in E). \] It is nowhere-zero if additionally $\phi(e)\neq0$ on every edge. Reversing the orientation of one edge and negating its value preserves these conditions, so existence is independent of the initially chosen orientation.

Tutte's $5$-flow conjecture asserts that every bridgeless $G$ admits a nowhere-zero integer $5$-flow. Thus each edge must carry one of $\pm1,\pm2,\pm3,\pm4$, with exact integer conservation at every vertex. Equivalently, an orientation may be chosen so all values belong to $\{1,2,3,4\}$.

Bridgelessness is necessary: summing conservation over one component after deleting a bridge forces its value to be zero. Components and isolated vertices cause no additional condition; they may be handled independently. The bound five is uniform over all orders and degrees, rather than a bound allowed to depend on the graph.

Short English statement

Can every bridgeless graph carry a conserved nonzero integer flow with each edge value having magnitude at most four?

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.

Literature and the boundedness issue.

The primary paper [R1] gives proofs of Seymour's theorem that every bridgeless graph has a nowhere-zero six-flow. That is a prior theorem, not a five-flow proof. We first give an elementary construction showing why bridges are the exact obstruction to an integer flow with some finite bound, then obtain the required bound on two substantial special classes. All conservation equations below are integer equations, not merely congruences modulo five.

Bridges versus cycle coverage.

If $e$ is a bridge, sum conservation over one component of $G-e$. All internal contributions cancel, leaving $\pm\phi(e)=0$, so a nowhere-zero flow is impossible. Conversely, every edge in a bridgeless loopless multigraph lies on a cycle: after deleting it there remains a path between its endpoints. A pair of parallel edges can form a cycle of length two. Choose finitely many cycles $C_0,\ldots,C_{r-1}$ covering all edges and assume here that $E(G)\ne\varnothing$, so $r\ge1$; an edgeless graph already has the empty two-flow. Orient each chosen cycle cyclically. Relative to one fixed reference orientation, its unit circulation is a vector $z_i\in\{-1,0,1\}^{E}$. Put \[ \phi=\sum_{i=0}^{r-1}2^i z_i. \] Each vector satisfies conservation, so their sum does. For an edge $e$, let $j$ be the largest index with $z_j(e)\ne0$. Its contribution has magnitude $2^j$, strictly greater than $\sum_{i<j}2^i=2^j-1$. Hence $\phi(e)\ne0$, and $|\phi(e)|\le2^r-1$. We have constructed a $2^r$-flow without using a general bounded-flow theorem. The exponential bound explains exactly what this construction fails to control.

Eulerian components.

If all degrees are even, every component with edges has a closed Euler tour. Orient its edges along that tour and assign value one. Every arrival is paired with a departure, so conservation holds at every vertex. Equivalently, decompose the edges into cycles and orient them separately; edge-disjointness avoids cancellation altogether. This is a nowhere-zero two-flow and therefore satisfies the five-flow requirement. Isolated vertices impose the empty equation and need no separate adjustment.

Three-edge-colourable cubic graphs.

Let the colour classes of a proper three-edge-colouring be $M_1,M_2,M_3$. Every vertex meets one edge of each colour. The graphs with edge sets $M_1\cup M_2$ and $M_2\cup M_3$ are disjoint unions of cycles, so admit unit circulations $x,y$, extended by zero outside their respective supports. The integer circulation \[ f=x+2y \] has magnitude one on $M_1$, magnitude two on $M_3$, and magnitude one or three on $M_2$: there its value is $\pm1\pm2$. Thus it never vanishes and has magnitude at most three. This proves a four-flow, stronger than the requested five-flow, for every such cubic graph. The argument works for parallel edges as well because the two-colour components are still even cycles, including length two.

Why the construction does not extend automatically.

A bridgeless cubic graph need not admit three edge colours. An arbitrary cycle cover can have many overlapping supports, and assigning all cycles weight one can produce cancellations. Powers of two prevent cancellation but lose a uniform bound. Even finding two spanning even subgraphs is not automatic: their union must cover every edge for the displayed $x+2y$ argument to be nowhere zero. The proof does not establish that coverage property for an arbitrary bridgeless graph.

Verification and final status.

The root batch script verifies a concrete $K_4$ certificate by computing the signed incidence sums of both circulations and their weighted sum. The bridge obstruction and largest-term estimate are exact symbolic arguments valid at every size. UNRESOLVED. Eulerian graphs and three-edge-colourable cubic graphs satisfy the target here. Controlling overlapping cycle circulations by the fixed magnitudes one through four in every bridgeless graph is the missing universal step.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3214 (OPG-126), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, 5-flow conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/5_flow_conjecture.
• R1 Matt DeVos, Edita Rollová and Robert Šámal, A new proof of Seymour's 6-flow theorem, arXiv:1512.06214. Primary abstract checked 1 October 2026. https://arxiv.org/abs/1512.06214.