Tutte's 3-Flow Conjecture

Tutte's 3-flow conjecture (posed in 1972) asserts that every 4-edge-connected finite graph admits a nowhere-zero 3-flow, an orientation of the edges together with flow values in $\{\pm1,\pm2\}$ that conserve flow at every vertex; equivalently, every 4-edge-connected graph has a modulo-3 orientation, an orientation in which each vertex has indegree congruent to outdegree modulo 3. Thomassen's 2012 paper 'The weak 3-flow conjecture and the weak circular flow conjecture' proved the weak version at 8-edge-connectivity. The best known general result is that 6-edge-connectivity suffices (Lovász, Thomassen, Wu, Zhang, 2013); the conjecture asserts that 4 suffices, and it remains open.

Background

An integer flow on a graph is built in two steps: first orient every edge, then assign to each edge a nonzero integer so that, at every vertex, the total value on edges directed into the vertex equals the total value on edges directed out. If all values can be chosen from $\{\pm1,\dots,\pm(k-1)\}$, the result is a nowhere-zero $k$-flow. Flow conservation forces the value 0 on any bridge (an edge whose deletion disconnects the graph), so only bridgeless graphs admit nowhere-zero flows. The edge-connectivity $\lambda(G)$ is the minimum number of edges whose deletion disconnects $G$, and it is the natural connectivity parameter for flow problems. In this language Tutte's celebrated 5-flow conjecture says every bridgeless graph has a nowhere-zero 5-flow, and his 3-flow conjecture (1972) says that $\lambda(G)\ge 4$ already guarantees a nowhere-zero 3-flow. A standard reformulation: a graph has a nowhere-zero 3-flow if and only if it has a modulo-3 orientation, an orientation in which indegree is congruent to outdegree modulo 3 at every vertex (each edge of value $\pm1$ or $\pm2$ reduces mod 3 to a directed edge counted with sign). By planar duality, the planar case of the 3-flow conjecture is equivalent to Grötzsch's classical theorem that every triangle-free planar graph is 3-colorable. Jaeger's 1984 circular flow conjecture generalized the conjecture: for every odd $k$, every $(2k-2)$-edge-connected graph should admit a modulo-$k$ orientation; writing $k=2p+1$ this says every $4p$-edge-connected graph has a modulo-$(2p+1)$-orientation, equivalently a nowhere-zero circular $(2+1/p)$-flow, and the case $p=1$ is exactly Tutte's 3-flow conjecture. Thomassen (2012) proved the weak versions: every 8-edge-connected multigraph has a modulo-3 orientation (with arbitrary prescribed outdegrees mod 3), and every $(2k^2+k)$-edge-connected multigraph has prescribed outdegrees modulo $k$; he also proved from this that highly edge-connected graphs decompose into stars. Lovász, Thomassen, Wu, and Zhang (2013) improved the thresholds to 6-edge-connected for nowhere-zero 3-flows and $(3k-3)$-edge-connected for modulo-$k$ orientations, introducing entropy-based orientation arguments; no better general bound has been found since. A stronger conjecture of Jaeger, Linial, Payan, and Tarsi (1992) predicts that every 5-edge-connected graph is $\mathbb{Z}_3$-connected, meaning every admissible prescription of the outdegree-minus-indegree residue mod 3 can be realized; this implies the 3-flow conjecture, and its best known case is again 6-edge-connected. Kochol's reductions (recorded in Hasanvand 2016 and in Li–Li–Liu 2025) show the conjecture suffices to verify for 5-edge-connected graphs and, equivalently, for 5-regular 4-edge-connected graphs (orientations with every indegree equal to 1 or 4). The full-strength conjecture at 4-edge-connectivity is the target: closing the gap between the known threshold 6 and the conjectured threshold 4.

Problem Statement

Does every finite 4-edge-connected graph (multiple edges allowed, no loops) admit a nowhere-zero 3-flow? Equivalently, does every finite graph of edge-connectivity at least 4 admit a modulo-3 orientation, that is, an orientation in which every vertex has indegree congruent to outdegree modulo 3? This is Tutte's 3-flow conjecture in its standard full-strength form, the $k=3$ case of Jaeger's circular flow conjecture and the unweakened form of the 'weak 3-flow conjecture' proved at 8-edge-connectivity in the source paper. The conjecture makes no restriction to planar, bounded-genus, bounded-independence, regular, or random graphs: a positive answer must establish the 3-flow for all 4-edge-connected graphs at once; a negative answer consists of a single explicit 4-edge-connected graph with no nowhere-zero 3-flow. The gap to close is between the conjectured threshold 4 and the best established threshold 6.

References

1. Carsten Thomassen (2012), 'The weak 3-flow conjecture and the weak circular flow conjecture', Journal of Combinatorial Theory, Series B 102(2):521-529. DOI: 10.1016/j.jctb.2011.09.003. https://doi.org/10.1016/j.jctb.2011.09.003
2. László Miklós Lovász, Carsten Thomassen, Yezhou Wu, Cun-Quan Zhang (2013), 'Nowhere-zero 3-flows and modulo k-orientations', Journal of Combinatorial Theory, Series B 103(5):587-598. DOI: 10.1016/j.jctb.2013.06.003. https://doi.org/10.1016/j.jctb.2013.06.003
3. Carsten Thomassen (2014), 'Group flow, complex flow, unit vector flow, and the (2+epsilon)-flow conjecture', Journal of Combinatorial Theory, Series B 108:81-91. DOI: 10.1016/j.jctb.2014.02.012. https://doi.org/10.1016/j.jctb.2014.02.012
4. Miaomiao Han, Jiaao Li, Yezhou Wu, Cun-Quan Zhang (2018), 'Counterexamples to Jaeger's Circular Flow Conjecture', Journal of Combinatorial Theory, Series B 131:1-11. DOI: 10.1016/j.jctb.2018.01.002. https://doi.org/10.1016/j.jctb.2018.01.002
5. Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le, Martin Merker, Stéphan Thomassé (2017), 'A proof of the Barát-Thomassen conjecture', Journal of Combinatorial Theory, Series B 124:39-55. DOI: 10.1016/j.jctb.2016.12.006. https://doi.org/10.1016/j.jctb.2016.12.006
6. Jiaao Li, Yulai Ma, Zhengke Miao, Yongtang Shi, Weifan Wang, Cun-Quan Zhang (2022), 'Nowhere-zero 3-flows in toroidal graphs', Journal of Combinatorial Theory, Series B 153:61-80. DOI: 10.1016/j.jctb.2021.11.001. https://doi.org/10.1016/j.jctb.2021.11.001
7. Jiaao Li, Rong Luo, Yi Wang (2018), 'Nowhere-zero 3-flow of graphs with small independence number', Discrete Mathematics 341:42-50. DOI: 10.1016/j.disc.2017.06.022. https://doi.org/10.1016/j.disc.2017.06.022
8. Miaomiao Han, Hong-Jian Lai, Jiaao Li (2018), 'Modulo orientations with bounded independence number', Discrete Applied Mathematics 247:14-22. DOI: 10.1016/j.dam.2018.01.016. https://doi.org/10.1016/j.dam.2018.01.016
9. Jiaao Li, Xinyuan Li, Jianbing Liu (2025), 'Modulo k-orientations of random regular graphs', Discrete Applied Mathematics 377:269-288. DOI: 10.1016/j.dam.2025.06.060. https://doi.org/10.1016/j.dam.2025.06.060
10. Jamie V. de Jong, R. Bruce Richter (2023), 'Strong 3-Flow Conjecture for projective planar graphs', Journal of Graph Theory 103(3):635-660. DOI: 10.1002/jgt.22939. https://doi.org/10.1002/jgt.22939
11. Morteza Hasanvand (2016), 'Tutte's 3-Flow Conjecture in 3-tree-connected graphs', arXiv:1611.02231. https://arxiv.org/abs/1611.02231
12. Junyang Zhang, Sanming Zhou (2022), 'Nowhere-zero 3-flows in Cayley graphs on supersolvable groups', arXiv:2203.02971; journal version Journal of Combinatorial Theory, Series A 204:105852 (2024). DOI: 10.1016/j.jcta.2023.105852. https://doi.org/10.1016/j.jcta.2023.105852
13. F. Jaeger (1984), 'On circular flows in graphs', in Finite and Infinite Sets (Colloquia Mathematica Societatis János Bolyai 37), pp. 391-402. DOI: 10.1016/b978-0-444-86893-0.50031-0. https://doi.org/10.1016/b978-0-444-86893-0.50031-0
14. Milad Ahanjideh, István Kovács (2026), 'Nowhere-zero 3-flows in Cayley graphs on solvable groups of twice square-free order', arXiv:2603.24175. https://arxiv.org/abs/2603.24175
15. François Jaeger, Nathan Linial, Charles Payan, Michael Tarsi (1992), 'Group connectivity of graphs—A nonhomogeneous analogue of nowhere-zero flow properties', Journal of Combinatorial Theory, Series B 56(2):165-182. DOI: 10.1016/0095-8956(92)90016-q. https://doi.org/10.1016/0095-8956(92)90016-q