In August 2026, Yuta Inoue, Ken-ichi Kawarabayashi, Ritarou Matsuo, Atsuyuki Miyashita, Bojan Mohar, and Tomohiro Sonobe (Inoue et al. 2026) completed the proof of a famous conjecture of Tutte from 1966. The result is closely connected with the Four Colour Theorem and forms an important part of the still largely mysterious theory of nowhere-zero flows.
Let be a graph. An orientation of is obtained by choosing a direction for every edge. For a vertex , let and denote the sets of edges directed out of and into , respectively.
For an integer , a nowhere-zero -flow is an orientation of together with a function
such that
for every vertex . This concept was introduced by Tutte (Tutte 1949).
A connected graph is -edge-connected if it remains connected after deleting fewer than edges. A graph is bridgeless if it has no edge whose deletion disconnects a component.
The Petersen graph is the graph on vertices
with subscripts modulo , and edges
for . Thus the form a pentagon, the form a five-pointed star, and each is joined to .
A graph is a minor of if can be obtained from by deleting vertices or edges and by contracting edges.
Tutte formulated three famous conjectures about nowhere-zero flows:
The -flow conjecture. Every -edge-connected graph has a nowhere-zero -flow.
The -flow conjecture. Every bridgeless graph without the Petersen graph as a minor has a nowhere-zero -flow.
The -flow conjecture. Every bridgeless graph has a nowhere-zero -flow.
There is a pleasing balance between these three conjectures. The -flow conjecture asks for the smallest genuinely interesting flow value, but compensates by assuming strong connectivity. The -flow conjecture applies to the largest possible class of graphs: a graph containing a bridge cannot have a nowhere-zero flow of any size. The number cannot simply be replaced by , because the Petersen graph is bridgeless but has no nowhere-zero -flow.
The -flow conjecture sits naturally between these two extremes. It predicts that the Petersen graph is, in a precise minor-theoretic sense, the only essential obstruction to a nowhere-zero -flow.
All three conjectures remain open. There are, however, very strong partial results. Jaeger proved that every -edge-connected graph has a nowhere-zero -flow (Jaeger 1979). Thomassen proved that every -edge-connected graph has a nowhere-zero -flow (Thomassen 2012), and Lov’asz, Thomassen, Wu, and Zhang improved to (Lovász et al. 2013):
Kochol showed that proving this for -edge-connected graphs would already imply the full -flow conjecture (Kochol 2001).
For the -flow conjecture, Seymour proved in 1981 (Seymour 1981) that
The 2026 result concerns the -flow conjecture for cubic graphs, that is, graphs in which every vertex has degree .
A proper -edge-colouring assigns one of three colours to every edge so that edges meeting at a common vertex receive different colours. For cubic graphs,
Indeed, one may identify the three colours with the three nonzero elements of
Thus the cubic case of Tutte’s -flow conjecture becomes the following statement.
Tutte’s three-edge-colouring conjecture. Every -connected cubic graph without the Petersen graph as a minor is -edge-colourable.
Here a connected graph with at least three vertices is -connected if deleting any one vertex leaves it connected.
The conjecture is closely related to the Four Colour Theorem. One equivalent form of that theorem says that every -connected cubic planar graph is -edge-colourable. Tutte’s conjecture replaces planarity by the much weaker condition of excluding the Petersen graph as a minor.
In 1997, Robertson, Seymour, and Thomas (Robertson et al. 1997) reduced the conjecture to two special classes of graphs.
A graph is apex if deleting one vertex makes it planar. A graph is doublecross if it can be drawn in the plane with only two crossings, both on the boundary of the same face.
They showed that it is enough to prove:
every -connected doublecross cubic graph is -edge-colourable;
every -connected apex cubic graph is -edge-colourable.
The doublecross case was proved by Edwards, Sanders, Seymour, and Thomas (Edwards et al. 2016). The apex case remained.
In 2026, Inoue, Kawarabayashi, Matsuo, Miyashita, Mohar, and Sonobe proved (Inoue et al. 2026):
Theorem. Every -connected apex cubic graph is -edge-colourable.
Together with the previous reduction and the doublecross case, this proves Tutte’s three-edge-colouring conjecture.
Equivalently,
The proof is computer-assisted and uses the same broad ideas of reducible configurations and discharging that appear in the Four Colour Theorem. It is also constructive: the authors obtain an algorithm for finding a -edge-colouring of an apex cubic graph.
It is important that this does not prove Tutte’s full -flow conjecture. The general -flow, -flow, and -flow conjectures all remain open. What has now been settled is the cubic case of the -flow conjecture, sixty years after Tutte formulated it.