gpt 6 astra ultra attempt on Math-303

Tutte's 5-Flow Conjecture

Definitions and mathematical statement

An edge is a bridge if removing it increases the number of connected components. For an orientation of a finite graph, an integer flow assigns $f(e)$ to each edge and satisfies Kirchhoff conservation \[ \sum_{e\text{ outgoing at }v}f(e)=\sum_{e\text{ incoming at }v}f(e) \quad\text{at every vertex }v. \] The conjecture says every bridgeless graph has such a flow with $f(e)\in\{-4,-3,-2,-1,1,2,3,4\}$ on every edge. Negative values are interpreted relative to the chosen orientation. In the usual multigraph convention, loops contribute to both sides. No planarity or bounded-genus assumption is imposed; the empty edge set causes no obstruction.

Formulation and concept references: [S1].

Short English statement

Can every bridgeless finite graph carry a nowhere-zero integer flow whose absolute edge values are at most four?

Research attempt

GPT-6 Astra Ultra, 27 September 2026. Status: UNRESOLVED.

The first missing step is a simultaneous avoidance of zero on every edge while keeping the flow in a fixed small set. Conservation alone is easy to enforce by combining cycles, and bridgelessness ensures that no individual edge is forced to be zero. The conjecture asks for a global combination with absolute values at most four. The bounded-genus theorem in [S1] treats a substantial restricted class, with Euler genus at most twenty in its stated result; it does not impose a genus restriction on the problem above. This attempt proves an unrestricted but exponentially bounded integer-flow construction, an elementary equivalence with nonzero flows modulo five, and stronger bounds for two specific subclasses. It then identifies the finite-field obstruction that prevents these ingredients from completing the argument.

What bridgelessness supplies exactly

Fix an arbitrary orientation. If $e$ is a bridge, sum conservation over one component of the graph obtained by deleting $e$. Contributions of internal edges cancel, leaving $f(e)=0$. A nowhere-zero flow is therefore impossible in the presence of a bridge. Loops cancel locally and require no special conservation adjustment; a loop may receive value one. Disconnected graphs can be treated component by component, including isolated vertices.

Conversely, every nonloop edge of a bridgeless graph belongs to a cycle. Indeed, after deleting the edge its endpoints are still connected, and a path between them together with the edge contains the required cycle. A loop itself is a cycle. For each of the $m$ edges, choose such a cycle containing it, and let $g_j$ be its signed unit circulation in the fixed orientation. Thus every coordinate of $g_j$ belongs to $\{-1,0,1\}$, and $Bg_j=0$ for the incidence matrix $B$.

The sum \[ f=\sum_{j=0}^{m-1}2^j g_j \tag{299.1} \] is an integer flow. At any given edge, let $j_*$ be the largest index whose cycle uses it. The contribution of that cycle has magnitude $2^{j_*}$, while all earlier contributions together have magnitude at most $2^{j_*}-1$. They cannot cancel it. Thus \[ 1\le |f(e)|\le 2^m-1\qquad(e\in E). \tag{299.2} \] For $m=0$, the empty flow already satisfies the target. This gives a completely elementary sufficiency proof for existence of a nowhere-zero integer flow with some finite bound. The quantitative jump from $2^m-1$ to four is precisely what this lexicographic domination method does not achieve.

Two subclasses with a stronger bound

If every vertex has even degree, orient each connected component along an Euler tour and give every edge value one. Each arrival at a vertex is paired with a departure, so this is a nowhere-zero flow with absolute value one. Loops have their usual contribution of two to undirected degree and work in the same construction.

More generally, suppose two even subgraphs cover all the edges. Orient Euler tours in them, producing signed flows $g,h$ with coordinates in $\{-1,0,1\}$. Then \[ f=g+2h \tag{299.3} \] is nonzero on every covered edge: where both occur its value is one of $\pm1,\pm3$, and where only one occurs it is $\pm1$ or $\pm2$. Thus $299.3$ is a nowhere-zero flow of absolute value at most three.

For example, in a loopless cubic graph with a proper three-edge-coloring, the subgraphs on colors $\{1,2\}$ and $\{2,3\}$ have degree two at every vertex and cover the edges. This gives the stated bound directly. It does not show that an arbitrary bridgeless cubic graph has such a coloring or such a two-subgraph cover. Those extra hypotheses cannot be inferred just from every edge lying on a cycle.

Lifting a nonzero flow modulo five

The integer formulation is equivalent to finding a flow over $\mathbb F_5$ with every edge value nonzero. One direction is immediate: reduce an integer flow with absolute values at most four modulo five. For the other direction, let $r_e\in\{1,2,3,4\}$ represent a nonzero modular flow. Then \[ Br=5b \] for an integer vector $b$, so the fractional vector $z=r/5$ satisfies $Bz=b$ and $0\le z_e\le1$.

We can round $z$ to an integral vector in the same box while preserving $Bz$. Consider the undirected subgraph of nonloop edges on which $z_e$ is strictly fractional. It has no vertex of degree one. Otherwise the incidence equation at that vertex, after subtracting all integral edge contributions, would say that a single number strictly between $-1$ and $1$, different from zero, is an integer. If fractional nonloop edges remain, their subgraph therefore contains an undirected cycle, allowing a two-edge cycle when edges are parallel.

Give this cycle its signed circulation $c$. Vary $z$ along $z+tc$, preserving $Bz=b$, until the first fractional coordinate reaches zero or one. Such a nonzero step exists, because every affected coordinate begins in the open interval. No formerly integral coordinate is changed, and at least one fewer coordinate is fractional. Fractional loops can simply be rounded separately, since their incidence columns vanish. After finitely many steps, \[ z\in\{0,1\}^E,\qquad Bz=b. \] Now set \[ f=r-5z. \tag{299.4} \] Its coordinates belong to $\{1,2,3,4,-4,-3,-2,-1\}$ and $Bf=5b-5b=0$. This proves the equivalence, including parallel edges and loops, without assuming an integral linear programming theorem.

The lifting procedure is effective and has at most $m$ rounding steps. It repairs a possible gap in a modular strategy: small residue representatives need not themselves satisfy integer conservation, but $299.4$ supplies the required correction. The hard part is finding the initial modular flow with no zero coordinates.

Why a union of proper kernels is still a problem

For a graph with $c$ connected components, the $\mathbb F_5$ flow space has dimension $m-|V|+c$. This follows by selecting a spanning forest: its incidence columns are independent, and every nonforest edge supplies one fundamental cycle. Loops are nonforest edges with their own cycle coordinate.

If the graph is bridgeless, evaluation at any edge is a nonzero linear functional on this space, because a cycle flow uses that edge. For a uniformly random flow, therefore, \[ \Pr(f(e)=0)=1/5. \] The union bound only gives \[ \Pr(\hbox{some edge is zero})\le m/5, \tag{299.5} \] which establishes existence by this route only when $m<5$. It does not improve as the dimension of the flow space grows.

Over an infinite field, a finite union of proper linear subspaces cannot cover the whole vector space. The analogous assertion over $\mathbb F_5$ is false: the six one-dimensional subspaces of $\mathbb F_5^2$ cover all twenty-five vectors. Every one is the kernel of a nonzero linear functional. Thus the facts that every coordinate kernel is proper and that each has relative size $1/5$ are not sufficient, by themselves, to prove a point outside their union.

This abstract arrangement is not asserted to arise as the coordinate kernels of a bridgeless graph and is not a counterexample to the conjecture. Rather, a successful argument must exploit additional structure of graphic flow spaces. Likewise, reducing $299.1$ modulo five may create zero coordinates: domination of integer magnitudes is lost modulo a fixed prime. Independence or locality needed for a stronger probabilistic argument must be proved, not inferred from the existence of many cycles.

Verification and outcome

The saved checks enumerate small bridgeless graphs, construct the exponential-bound flow, search their finite flow spaces for nonzero modular flows, and verify the integer lift by exact conservation. Separate examples include parallel edges and loops. These tests examine the reductions and boundary conventions, not all bridgeless graphs. The two-even-subgraph construction is checked independently of the unrestricted search.

UNRESOLVED. Bridgelessness gives an elementary nowhere-zero integer flow, and a nowhere-zero modular-five flow would give exactly the required integer bound. The missing theorem is global avoidance of all coordinate kernels in every bridgeless graphic flow space over $\mathbb F_5$; neither the union bound nor unrestricted cycle domination proves it.

Sources

• S1 Jiaao Li and Bo Su, Nowhere-zero 5-flows for graphs with bounded genus $2025$, Abstract. https://www.ort.shu.edu.cn/EN/abstract/abstract21516.shtml. Formulation source.