Tutte's 4-flow conjecture: nowhere-zero 4-flows in bridgeless graphs with no Petersen minor

Tutte's 4-flow conjecture (1966) asserts that every finite bridgeless graph with no minor isomorphic to the Petersen graph admits a nowhere-zero 4-flow — that is, the Petersen graph is the unique minor obstruction to 4-flows. The conjecture implies the Four-Color Theorem via planar duality, contains the still-open Tutte edge-colouring conjecture as its cubic case, and is one of the three central integer-flow conjectures of structural graph theory. As of August 2026 it remains open. The planar case is the Four-Color Theorem, and available results settle the conjecture for every graph excluding a proper minor of the Petersen graph (the $P-e$ case by Thomas and Thomson in 2000, the $P/e$ case by a 2026 preprint of Pintér), so the surviving core consists of bridgeless graphs with no Petersen minor that contain every proper minor of the Petersen graph, and a fortiori the cubic case is still unresolved.

Background

An integer flow on a finite undirected graph $G$ is defined after orienting its edges: it assigns to each edge $f$ an integer $\varphi(f)$ such that, at every vertex, the sum of the values on incoming edges equals the sum on outgoing edges. The flow is nowhere-zero if $\varphi(f)\neq 0$ for every edge, and a nowhere-zero 4-flow takes values in $\{\pm1,\pm2,\pm3\}$ . By a classical theorem of Tutte, a graph admits a nowhere-zero $k$ -flow if and only if it admits one over any fixed abelian group of order $k$ , for instance $\Gamma=\mathbb{Z}_2\times\mathbb{Z}_2$ with its three nonzero elements, in which form the conservation law is a parity condition. A bridge (cut-edge) must carry value $0$ in every flow, so bridgeless (2-edge-connected) graphs are the natural domain. Two standard equivalences make the notion concrete: a graph has a nowhere-zero 4-flow if and only if its edge set is the union of two even subgraphs (subgraphs in which every vertex has even degree), and on a loopless cubic graph a nowhere-zero 4-flow is equivalent to a proper 3-edge-colouring (a Tait colouring); a connected bridgeless cubic graph without one is called a snark.

The Petersen graph $P$ is the cubic graph on ten vertices consisting of an outer 5-cycle, an inner 5-pointed star, and five spokes joining them. It is bridgeless, has girth five (the girth of a graph is the length of its shortest cycle), is the smallest snark, and has flow number 5: it admits a nowhere-zero 5-flow but no nowhere-zero 4-flow, and it is the smallest bridgeless graph with this property. A graph $H$ is a minor of $G$ if $H$ can be obtained from a subgraph of $G$ by contracting edges; since the 4-flow property passes to bridgeless minors, excluding a minor is the natural form of an obstruction theorem. Tutte's 4-flow conjecture (1966) asserts that $P$ is the only obstruction: every finite bridgeless graph with no minor isomorphic to $P$ admits a nowhere-zero 4-flow; equivalently, every bridgeless graph without a nowhere-zero 4-flow contains the Petersen graph as a minor.

The conjecture is one of three flow conjectures in Tutte's 1966 paper (the 3-flow conjecture for 4-edge-connected graphs, the 4-flow conjecture, and the 5-flow conjecture for all bridgeless graphs); of these, only the weaker 6-flow analogue is a theorem. For a connected bridgeless plane graph, Tutte's duality identifies nowhere-zero 4-flows of the graph with proper vertex 4-colourings of its planar dual, so the planar case of the conjecture is exactly the Four-Color Theorem, available through the computer-assisted proof of Robertson, Sanders, Seymour and Thomas (1997); since planar graphs contain no Petersen minor, the conjecture implies the Four-Color Theorem and is viewed as a far-reaching nonplanar generalization of it. Restricted to loopless cubic graphs, the conjecture is Tutte's edge-colouring conjecture: every bridgeless cubic graph with no Petersen minor is 3-edge-colourable, that is, every snark contains a Petersen minor. This cubic case is itself open in the published literature: Robertson, Seymour and Thomas (1997) reduced it to two families of almost planar cubic graphs, and the reduction has not been completed in print, although the accompanying structural theory shows, for example, that every cubic graph of girth at least six contains a subdivision of $P$ . With heavy computer assistance, the surface-restricted cases were recently settled: every cyclically 4-edge-connected cubic graph (no edge cut of fewer than four edges separates two cycles) embedded in the projective plane (2024) or the torus (2025) is 3-edge-colourable up to explicitly described 'Petersen-like' exceptions, proving a long-standing 1968 conjecture on toroidal cubic graphs, and 4- and 5-regular projective planar $r$ -graphs (regular graphs in which every odd vertex set sends out at least $r$ edges) with no Petersen minor are class 1, that is, have edge-chromatic number equal to their maximum degree (2025).

For bridgeless graphs of arbitrary vertex degrees, the conjecture is proved whenever some proper minor of $P$ is excluded. Kilakos and Shepherd (1996) proved the cubic case for graphs with no $P-e$ minor, where $e$ is an edge of $P$ . Thomas and Thomson (2000) proved that every 2-edge-connected graph with no $P-e$ minor has a nowhere-zero 4-flow, deducing it from their structure theorem that every graph of minimum degree at least three and girth at least five has a minor isomorphic to one of four named graphs (Triplex, Petersen, Dodecahedron, Basket). Wang, Zhang and Zhang (2009) settled the class excluding $P^{(3)}$ , the Petersen graph with three edges of a perfect matching contracted. Pintér (2026, preprint) reached the last maximal class: every finite bridgeless multigraph with no $Q=P/e$ minor (one edge contracted) admits a nowhere-zero 4-flow, building on the Thomas–Thomson framework and the Norin–Thomas theorem that an almost 4-connected nonplanar graph containing a subdivision of an almost 4-connected triangle-free planar graph $H$ contains a jump or cross extension of $H$ as a minor (a jump extension adds one edge joining two vertices of $H$ that lie on no common facial cycle of the planar embedding, and a cross extension adds two edges joining two pairs of vertices that occur in alternating order along a facial cycle). Since every proper minor of $P$ is a minor of $P-e$ or of $Q$ , these results together cover all graphs that exclude at least one proper minor of $P$ ; any counterexample must therefore be a bridgeless graph with no Petersen minor that contains every proper minor of $P$ , in particular both $P-e$ and $P/e$ . Minimal-obstruction analysis further forces such a graph to be 3-connected, almost 4-connected (3-connected, and whenever the vertex set splits into two parts meeting in three vertices with no edges between their exclusive parts, one part has at most four vertices), of girth at least five, and of minimum degree at least three.

Problem Statement

Tutte's 4-flow conjecture. Prove or refute: every finite bridgeless undirected multigraph with no minor isomorphic to the Petersen graph $P$ admits a nowhere-zero 4-flow.

Here bridgeless means that no edge is a cut-edge; a minor is obtained by deleting vertices, deleting edges, and contracting non-loop edges (loops may be present and are harmless, since a loop can always carry an arbitrary nonzero flow value); and a nowhere-zero 4-flow is, equivalently by Tutte's theorem, an assignment of a nonzero element of $\mathbb{Z}_2\times\mathbb{Z}_2$ to each edge of an orientation of the graph such that at every vertex the incoming values sum to the outgoing values. Equivalent formulations of the claim are: (i) the edge set of every such graph is the union of two even subgraphs; (ii) every bridgeless graph without a nowhere-zero 4-flow contains the Petersen graph as a minor; (iii) in the loopless cubic case, every bridgeless cubic graph with no Petersen minor is 3-edge-colourable (Tutte's edge-colouring conjecture, which is the cubic case of this problem and is itself open).

Derived narrowing, not a restriction of the claim: by the theorem of Thomas and Thomson (2000) and the preprint of Pintér (2026), the claim already holds for graphs excluding any proper minor of $P$ , so it suffices to consider bridgeless graphs with no Petersen minor that contain both $P-e$ (the Petersen graph with one edge deleted) and $P/e$ (the Petersen graph with one edge contracted) as minors (with only the peer-reviewed results, at least graphs containing a $P-e$ minor). A positive answer must establish the flow for all such graphs, including the cubic ones; a single verified finite counterexample — a bridgeless graph with no Petersen minor admitting no nowhere-zero 4-flow — refutes the conjecture.

References

W. T. Tutte, On the algebraic theory of graph colorings, Journal of Combinatorial Theory 1 (1966), 15–50. doi:10.1016/S0021-9800(66)80004-2, https://doi.org/10.1016/S0021-9800(66)80004-2
K. Kilakos and B. Shepherd, Excluding minors in cubic graphs, Combinatorics, Probability and Computing 5 (1996), 57–78. doi:10.1017/S0963548300001838, https://doi.org/10.1017/S0963548300001838
N. Robertson, D. Sanders, P. Seymour and R. Thomas, The four-colour theorem, Journal of Combinatorial Theory, Series B 70 (1997), 2–44. doi:10.1006/jctb.1997.1750, https://doi.org/10.1006/jctb.1997.1750
N. Robertson, P. Seymour and R. Thomas, Tutte's edge-colouring conjecture, Journal of Combinatorial Theory, Series B 70 (1997), 166–183. doi:10.1006/jctb.1997.1752, https://doi.org/10.1006/jctb.1997.1752
R. Thomas and J. M. Thomson, Excluding minors in nonplanar graphs of girth at least five, Combinatorics, Probability and Computing 9 (2000), 573–585. doi:10.1017/S0963548300004417, https://doi.org/10.1017/S0963548300004417
X. Wang, C.-Q. Zhang and T. Zhang, Nowhere-zero 4-flow in almost Petersen-minor free graphs, Discrete Mathematics 309 (2009), 1025–1032. doi:10.1016/j.disc.2007.11.055, https://doi.org/10.1016/j.disc.2007.11.055
S. Norin and R. Thomas, Non-planar extensions of subdivisions of planar graphs, Journal of Combinatorial Theory, Series B 121 (2016), 326–366. arXiv:1402.1999, doi:10.1016/j.jctb.2016.07.008, https://arxiv.org/abs/1402.1999
N. Robertson, P. D. Seymour and R. Thomas, Girth six cubic graphs have Petersen minors, arXiv:1405.0533 (manuscript dated 1997, posted 2014). https://arxiv.org/abs/1405.0533
V. Mkrtchyan, Sublinear bounds for nullity of flows and approximating Tutte's flow conjectures, arXiv:2008.07152 (2020). https://arxiv.org/abs/2008.07152
Y. Inoue, K. Kawarabayashi, A. Miyashita, B. Mohar and T. Sonobe, Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color Theorem, arXiv:2405.16586 (2024). https://arxiv.org/abs/2405.16586
Y. Inoue, K. Kawarabayashi, A. Miyashita, B. Mohar and T. Sonobe, Three-edge-coloring (Tait coloring) cubic graphs on the torus: A proof of Grünbaum's conjecture, arXiv:2505.07002 (2025). https://arxiv.org/abs/2505.07002
A. Kidner, E. Steffen and W. Yu, Edge-coloring 4- and 5-regular projective planar graphs with no Petersen-minor, arXiv:2512.14285 (2025). https://arxiv.org/abs/2512.14285
J. Pintér, Nowhere-zero 4-flows in graphs excluding a proper minor of the Petersen graph, arXiv:2607.22267 (2026; v2 of 9 Aug 2026, preprint). doi:10.48550/arXiv.2607.22267, https://arxiv.org/abs/2607.22267