gpt 6 astra ultra attempt on Math-354

3-flow conjecture

Definitions and mathematical statement

A finite loopless multigraph is $4$-edge-connected if deleting any set of at most three edges leaves it connected. A nowhere-zero integer $3$-flow consists of an orientation and edge values $f(e)\in\{-2,-1,1,2\}$ obeying conservation at every vertex: \[ \sum_{e\text{ enters }v} f(e)=\sum_{e\text{ leaves }v}f(e). \] Tutte's conjecture says every such graph has this flow. Parallel edges are allowed, and the one-vertex loopless case has the empty flow. Negative values can equivalently be made positive by reversing their edges. The requirement is ordinary zero-boundary conservation; it does not ask that every prescribed admissible boundary modulo three can be realized.

Formulation and concept references: [S1].

Short English statement

Does every four-edge-connected loopless multigraph admit a nonzero integer flow using only magnitudes one and two?

Research attempt

Status: UNRESOLVED. No construction of a nowhere-zero 3-flow for every 4-edge-connected multigraph is obtained. This attempt proves the equivalence with a modulo-three balanced orientation, including an explicit integral lifting argument, handles Eulerian and several bipartite cases, and isolates the failure of an unrestricted contraction-and-extension strategy. Finite orientation searches support these intermediate claims only.

Source audit and exact graph convention.

The source [S1], consulted on 27 September 2026, distinguishes ordinary nowhere-zero 3-flows from the stronger property of $\mathbb Z_3$-connectivity, and discusses special 4-edge-connected cases and the external theorem for 6-edge-connected graphs. Those results must not be silently substituted for the catalogue's general 4-edge-connected assertion. Parallel edges are allowed and counted with multiplicity. There are no loops. A cut counts edges, not distinct neighboring vertices, so a minimum-degree calculation by itself is not an edge-connectivity proof.

For a one-vertex loopless graph the edge set is empty and the empty flow meets the conservation and nowhere-zero conditions vacuously. In the nontrivial cases below, fix an orientation and let $B$ be its incidence matrix, with $+1$ at the tail and $-1$ at the head of each edge. Conservation for an integer edge vector $f$ means $Bf=0$.

1. From a 3-flow to a balanced orientation.

Reduce a nowhere-zero integer 3-flow modulo three. Every edge has nonzero value in $\mathbb F_3$, hence value 1 or 2. Reverse the orientation of an edge of value 2; its new value is $-2=1$ modulo three. Conservation remains valid. Thus all edges can be assigned value one in an orientation satisfying \[ d^+(v)-d^-(v)\equiv0\pmod3 \qquad\text{for every vertex }v. \] Call this a modulo-three balanced orientation. Conversely, such an orientation immediately gives a nowhere-zero flow over $\mathbb F_3$. To recover an integer 3-flow with absolute values at most two, one needs an additional lifting argument; simply interpreting the residue 1 as the integer 1 does not ensure integer conservation.

2. A complete integral lifting argument.

Suppose $B\mathbf1=3b$ for an integer vector $b$. The fractional vector $x=\mathbf1/3$ satisfies \[ Bx=b,\qquad 0\le x_e\le1. \] We show directly that there is a vector with the same constraints and every $x_e$ either zero or one. Consider the subgraph formed by edges whose coordinates are strictly between zero and one. If this subgraph is nonempty and has no undirected cycle, it has a leaf. At that leaf exactly one incident edge coordinate is nonintegral and all other coordinates are integers, contradicting the integer value of $(Bx)_v=b_v$. Hence the fractional edges contain an undirected cycle. This includes a cycle formed by two parallel edges, if present.

Choose a cyclic traversal and let $c_e$ be $+1$ or $-1$ on each cycle edge according as its chosen orientation agrees or disagrees with the traversal, and zero elsewhere. Then $Bc=0$. Vary $x$ to $x+tc$, choosing a nonzero value of $t$ at an endpoint of the interval for which all coordinates remain in $[0,1]$. At least one fractional coordinate becomes zero or one, no integral coordinate changes, and $Bx=b$ persists. Repeating removes at least one fractional edge at every step, so after finitely many steps we obtain an integral vector $x^*$ with the same constraints.

Now define \[ f=\mathbf1-3x^*. \] Every coordinate is either 1 or $-2$, and \[ Bf=B\mathbf1-3Bx^*=3b-3b=0. \] This is an integer nowhere-zero 3-flow in the original orientation. If desired, reverse the negatively weighted edges and use positive values 1 and 2. The proof gives the required lifting without assuming a total-unimodularity theorem, although it is a concrete instance of integral circulation rounding.

Therefore the catalogue problem is exactly the problem of finding a modulo-three balanced orientation in every 4-edge-connected graph. The difficult part is existence of that orientation, not the conversion from modular conservation to an integer flow.

3. Eulerian and bipartite subcases.

If every vertex has even degree, decompose each nontrivial connected component into edge-disjoint cycles and orient every cycle cyclically. At each vertex the number of incoming edges equals the number of outgoing edges. Assigning value one to every edge is then already an integer flow. The standard cycle decomposition follows by following unused edges until a cycle closes and deleting that cycle; every remaining degree stays even. Thus every loopless Eulerian multigraph has a nowhere-zero 2-flow, hence a 3-flow. In particular, this settles the 4-regular instances of the target, and more generally all of its even-degree instances.

If the graph is bipartite with parts $U,W$ and every degree is divisible by three, orient every edge from $U$ to $W$. The divergence is $d(v)$ on $U$ and $-d(v)$ on $W$, both zero modulo three. The lifting proof supplies an integer 3-flow. This argument does not require 4-edge-connectivity; it proves a different sufficient condition. It also does not say that every bipartite graph has a 3-flow, since the degree congruence was essential to this particular orientation.

4. The cubic obstruction explains the connectivity threshold.

For a vertex of degree three in a modulo-three balanced orientation, \[ 2d^+(v)-3\equiv0\pmod3. \] As $0\le d^+(v)\le3$, this forces $d^+(v)=0$ or $3$. Every vertex of a cubic graph must therefore be a sink or a source, and each edge joins the two different types. Hence a cubic graph with a 3-flow must be bipartite. Conversely, a bipartite cubic graph satisfies the preceding degree-divisibility condition and has a 3-flow. We have proved the exact characterization for cubic loopless multigraphs.

The complete graph $K_4$ is cubic, nonbipartite, and 3-edge-connected, so it has no nowhere-zero 3-flow. Its cut sizes are $s(4-s)$ for $s=1,2,3$, with minimum three. This verifies both the obstruction and its scope: it does not contradict the 4-edge-connected conjecture. Replacing 4-edge-connectivity by bridgelessness or by 3-edge-connectivity would make the assertion false.

Other degrees illustrate the orientation constraints without solving their simultaneous compatibility. At degree four one needs exactly two outgoing edges. At degree five the allowed outgoing degrees are one or four. At degree six they are zero, three, or six. Choosing an allowed value independently at each vertex does not construct an orientation: every edge contributes an outgoing incidence at exactly one endpoint, so all choices must fit globally.

5. Why contraction needs stronger boundary information.

Suppose a subgraph $H$ is contracted and a flow is found on the contracted graph. On expanding $H$, the already assigned external edges create a prescribed divergence at each vertex of $H$. Their total is zero modulo three, but their individual divergences need not vanish. To complete the flow, the internal edges must realize the opposite prescribed boundary.

The assertion that a graph can realize every boundary $\beta:V\to\mathbb F_3$ with $\sum_v\beta(v)=0$, using nonzero edge values, is the stronger property of $\mathbb Z_3$-connectivity. Having a flow for the zero boundary alone does not imply it. The distinction has a tiny exact example. A triangle has a zero-boundary flow by cyclic orientation. Prescribe instead $\beta(v)=1$ at all three vertices, which has total zero in $\mathbb F_3$. In any orientation with edge values normalized to one, each degree-two vertex would need \[ 2d^+(v)-2\equiv1\pmod3. \] For $d^+(v)\in\{0,1,2\}$ the only solution is $d^+(v)=0$. All three vertices would have to be sinks, which is impossible. Thus the triangle admits the ordinary flow but cannot realize this admissible boundary.

This example does not rule out every useful contraction argument. It shows exactly what such an argument must prove: the contracted part has enough boundary extension flexibility for the particular external data, or the outside flow can be chosen to produce a boundary it can realize. Invoking an ordinary zero-boundary flow on the contracted part is insufficient.

6. Cycle-space dimension is also insufficient by itself.

For a connected graph with $n$ vertices and $m$ edges, the space of $\mathbb F_3$-flows has dimension $m-n+1$. One proof chooses a spanning tree, assigns arbitrary values to the nontree edges, and solves conservation on tree edges by deleting leaves. The final vertex equation follows because total divergence is always zero. This also constructs a fundamental-cycle basis.

A nowhere-zero flow is a vector in this space outside every coordinate hyperplane $f_e=0$. If an edge is not a bridge, it lies on a cycle, so its coordinate is a nonzero linear functional on the flow space. For a uniformly chosen flow, that coordinate is uniform in $\mathbb F_3$, and its probability of being zero is $1/3$. A union bound only gives \[ \Pr(\text{some edge is zero})\le m/3, \] which is useless for the large graphs in question. The coordinate events are dependent; treating them as independent and concluding a positive probability from $(2/3)^m$ has no justification.

Thus a large-dimensional cycle space and absence of bridges do not alone prove that its coordinate hyperplanes fail to cover it. The cubic example $K_4$ already shows that they can cover a nontrivial flow space. Four-edge-connectivity imposes stronger cut conditions, but an argument converting them into an uncovered vector is still needed.

7. Finite orientation certificates and the missing theorem.

The offline diagnostic enumerates the simple graphs on at most six vertices whose nontrivial cuts all have size at least four. It searches for a modulo-three balanced orientation, then finds integral coordinates $x_e\in\{0,1\}$ with $Bx=b$, and checks the resulting $f_e=1-3x_e$ by exact integer conservation. It also checks three-vertex multigraphs with each pair multiplicity between zero and four and every cut of size at least four. The certificates record the actual edge values, not just a positive search flag. The negative $K_4$ case, positive $K_{3,3}$ case, and triangle boundary obstruction are separately verified by exhaustive orientations.

These finite cases test the multigraph convention, the degree congruences, and the lifting step. They do not prove that every larger 4-edge-connected graph has an admissible orientation. A complete proof must establish that global orientation theorem, or a valid inductive reduction preserving enough connectivity and boundary extension data. This attempt supplies the exact equivalence and several complete sufficient conditions, but no reduction reaching all remaining graphs. The unrestricted 3-flow conjecture remains unresolved here.

Sources

• S1 Chen and Ning, A note on nowhere-zero 3-flow and Z3-connectivity, Definition1.1 and Conjecture1.2, PDF printed p2. https://arxiv.org/pdf/1406.1554. Formulation source.