The Jaeger–Linial–Payan–Tarsi conjecture (Strong 3-Flow Conjecture): is every 5-edge-connected graph $\mathbb{Z}_3$-connected?

The source note "Tutte's 3-Flow Conjecture in 3-tree-connected graphs" (Hasanvand, arXiv:1611.02231) builds all of its results on one load-bearing open question, its Conjecture 1: the 1992 conjecture of Jaeger, Linial, Payan and Tarsi that every 5-edge-connected graph is $\mathbb{Z}_3$-connected, i.e., admits a modulo-3 orientation realizing every feasible prescribed out-degree function (also known as the Strong 3-Flow Conjecture). The note proves that this conjecture would extend $\mathbb{Z}_3$-connectivity from the edge-connectivity world to the tree-connectivity world — every 3-tree-connected graph would be $\mathbb{Z}_3$-connected — and, combined with Kochol's 2001 reduction, would settle Tutte's 3-flow conjecture and companion tree-decomposition conjectures of Barát–Gerbner. The conjecture remains open as of August 2026. The best unconditional edge-connectivity bound is still 6 (Lovász, Thomassen, Wu and Zhang, 2013), and the extensive web of partial verifications — line graphs, bounded independence number, planar and projective-planar graphs, graphs with four edge-disjoint spanning trees — leaves exactly the 5-edge-connected case unresolved. The problem is: prove or disprove that every 5-edge-connected graph is $\mathbb{Z}_3$-connected.

Background

A nowhere-zero $k$-flow on a graph $G$ assigns to each edge a nonzero integer of absolute value less than $k$, together with an edge orientation, so that flow is conserved at every vertex (total inflow equals total outflow). Tutte founded integer flow theory in the 1950s through its duality with face colorings of planar graphs, and in the early 1970s posed the 3-flow conjecture: every 4-edge-connected graph admits a nowhere-zero 3-flow. A graph is $k$-edge-connected if every cut separating a nonempty proper vertex subset from its complement contains at least $k$ edges; small cuts are the only known obstructions to 3-flows, which is why edge-connectivity governs the problem.

For 3-flows one can work modulo 3: a graph admits a nowhere-zero 3-flow if and only if it has an orientation in which the out-degree $d^+(v)$ of every vertex $v$ satisfies $d^+(v)\equiv 2d(v)\pmod 3$, where $d(v)$ is the degree of $v$. Jaeger, Linial, Payan and Tarsi (1992) introduced the stronger, "nonhomogeneous" notion of group connectivity, in which vertices may carry prescribed demands instead of demanding exact conservation: $G$ is $\mathbb{Z}_3$-connected if, for every mapping $p:V(G)\to\mathbb{Z}_3$ whose values sum to $|E(G)|$ modulo 3 (the only global obstruction), the graph has an orientation with $d^+(v)\equiv p(v)\pmod 3$ for every vertex $v$. Taking $p(v)\equiv 2d(v)\pmod 3$ recovers the nowhere-zero 3-flow, so every $\mathbb{Z}_3$-connected graph has a nowhere-zero 3-flow, and the converse fails (conservation at each vertex separately is weaker than realizing all admissible prescriptions simultaneously). Jaeger, Linial, Payan and Tarsi conjectured that every 5-edge-connected graph is $\mathbb{Z}_3$-connected; the assertion is often called the Strong 3-Flow Conjecture.

Two published reductions tie this conjecture to the surrounding theory. Kochol (2001) proved that Tutte's 3-flow conjecture is equivalent to its own restriction to 5-edge-connected graphs, so the Strong 3-Flow Conjecture implies Tutte's conjecture outright. Hasanvand (arXiv:1611.02231) then proved that the Strong 3-Flow Conjecture would also imply that every 3-tree-connected graph — a graph containing three edge-disjoint spanning trees; by the Nash-Williams–Tutte tree-packing theorem every 6-edge-connected graph is 3-tree-connected — is $\mathbb{Z}_3$-connected, extending the conjecture strictly beyond the edge-connectivity setting, and would settle the note's companion conjectures: the Barát–Gerbner conjecture that every $k$-tree-connected simple graph whose number of edges is divisible by $k$ can be edge-decomposed into copies of any fixed tree with $k$ edges, and the note's Conjecture 3 that every $k$-tree-connected graph admits a $p$-orientation over $\mathbb{Z}_k$ for every admissible $p$.

Unconditionally the frontier sits exactly one unit above the conjecture. Thomassen (2012) proved the weak 3-flow theorem: every 8-edge-connected graph has a nowhere-zero 3-flow. Lovász, Thomassen, Wu and Zhang (2013) proved that every 6-edge-connected graph is $\mathbb{Z}_3$-connected; their bar-amputation induction needs six parallel edges crossing each small cut, which is why the method stops at 6, and no improvement of the threshold has been found in the decade since. Many partial verifications support the conjecture: 5-edge-connected line graphs and 7-edge-connected triangular claw-free graphs (Lai, Li, Li, Liang and Yao, 2011); graphs with four edge-disjoint spanning trees (Han, Lai and Li, 2018); graphs satisfying a refined (6,4,3,3)-edge-connectivity condition (Kochol, 2019); 5-edge-connected graphs with independence number at most 3 (Qin, Zhang and Li, 2023); and planar graphs (de Jong, 2020) and projective-planar graphs (de Jong and Richter, 2023). For the weaker Tutte 3-flow conjecture the verified families include toroidal graphs (Li, Ma, Miao, Shi, Wang and Zhang, 2022), Cayley graphs on supersolvable groups and, most recently, on solvable groups of twice square-free order (Ahanjideh and Kovács, 2026), and asymptotically almost all 5-regular graphs (Prałat and Wormald, 2019).

Problem Statement

Determine the truth of the Strong 3-Flow Conjecture of Jaeger, Linial, Payan and Tarsi (Conjecture 1 of the source note): is every 5-edge-connected loopless graph $G$ (multiple edges allowed) $\mathbb{Z}_3$-connected? Equivalently, does every such $G$ admit, for each mapping $p:V(G)\to\mathbb{Z}_3$ with $|E(G)|\equiv\sum_{v\in V(G)}p(v)\pmod 3,$ an orientation of its edges whose out-degrees satisfy $d^+(v)\equiv p(v)\pmod 3$ for every vertex $v$? An affirmative answer would, through Kochol's 2001 reduction, settle Tutte's 3-flow conjecture (every 4-edge-connected graph admits a nowhere-zero 3-flow), and, by the main theorem of the source note, extend $\mathbb{Z}_3$-connectivity to every 3-tree-connected graph and imply its Conjectures 2 and 3 on tree-decompositions and $\mathbb{Z}_k$-orientations of $k$-tree-connected graphs. A negative answer consists of a single 5-edge-connected graph together with one admissible mapping $p$ that it cannot realize. Note that an answer to the weaker question of whether every 5-edge-connected graph merely admits a nowhere-zero 3-flow (no prescribed demands) would not by itself resolve this conjecture.

References

1. M. Hasanvand, Tutte's 3-Flow Conjecture in 3-tree-connected graphs, arXiv:1611.02231 (v2, 2022), DOI: 10.48550/arXiv.1611.02231, https://arxiv.org/abs/1611.02231
2. F. Jaeger, N. Linial, C. Payan, M. Tarsi, Group connectivity of graphs — a nonhomogeneous analogue of nowhere-zero flow properties, Journal of Combinatorial Theory, Series B 56 (1992) 165–182, DOI: 10.1016/0095-8956(92)90016-Q, https://doi.org/10.1016/0095-8956(92)90016-Q
3. M. Kochol, An equivalent version of the 3-flow conjecture, Journal of Combinatorial Theory, Series B 83 (2001) 258–261, DOI: 10.1006/jctb.2001.2054, https://doi.org/10.1006/jctb.2001.2054
4. L. M. Lovász, C. Thomassen, Y. Wu, C.-Q. Zhang, Nowhere-zero 3-flows and modulo k-orientations, Journal of Combinatorial Theory, Series B 103 (2013) 587–598, DOI: 10.1016/j.jctb.2013.06.003, https://doi.org/10.1016/j.jctb.2013.06.003
5. C. Thomassen, The weak 3-flow conjecture and the weak circular flow conjecture, Journal of Combinatorial Theory, Series B 102 (2012) 521–529, DOI: 10.1016/j.jctb.2011.09.003, https://doi.org/10.1016/j.jctb.2011.09.003
6. H.-J. Lai, H. Li, P. Li, Y. Liang, S. Yao, Group connectivity in line graphs, Discrete Mathematics 311 (2011) 2295–2307, DOI: 10.1016/j.disc.2011.07.017, https://doi.org/10.1016/j.disc.2011.07.017
7. M. Kochol, Equivalent versions of group-connectivity theorems and conjectures, Discrete Applied Mathematics 257 (2019) 350–352, DOI: 10.1016/j.dam.2018.10.010, https://doi.org/10.1016/j.dam.2018.10.010
8. M. Han, H.-J. Lai, J. Li, Nowhere-zero 3-flow and Z3-connectedness in graphs with four edge-disjoint spanning trees, Journal of Graph Theory 88 (2018) 577–591, DOI: 10.1002/jgt.22231, https://doi.org/10.1002/jgt.22231
9. C. Qin, X. Zhang, L. Li, Z3-connectivity of graphs with independence number at most 3, AIMS Mathematics 8 (2023) 3204–3209, DOI: 10.3934/math.2023164, https://doi.org/10.3934/math.2023164
10. J. V. de Jong, Two Strong 3-Flow Theorems for Planar Graphs, arXiv:2011.02140 (2020), DOI: 10.48550/arXiv.2011.02140, https://arxiv.org/abs/2011.02140
11. J. V. de Jong, R. B. Richter, Strong 3-Flow Conjecture for projective planar graphs, Journal of Graph Theory 103 (2023) 635–660, DOI: 10.1002/jgt.22939, https://doi.org/10.1002/jgt.22939
12. J. Li, Y. Ma, Z. Miao, Y. Shi, W. Wang, C.-Q. Zhang, Nowhere-zero 3-flows in toroidal graphs, Journal of Combinatorial Theory, Series B 153 (2022) 61–80, DOI: 10.1016/j.jctb.2021.11.001, https://doi.org/10.1016/j.jctb.2021.11.001
13. J. Li, Y. Ma, Z. Miao, Y. Shi, W. Wang, Nowhere-zero 3-flows in signed planar graphs, The Electronic Journal of Combinatorics 31 (2024), DOI: 10.37236/11892, https://doi.org/10.37236/11892
14. P. Prałat, N. Wormald, Almost all 5-regular graphs have a 3-flow, Journal of Graph Theory 93 (2019) 147–156, DOI: 10.1002/jgt.22478, https://doi.org/10.1002/jgt.22478
15. M. Ahanjideh, I. Kovács, Nowhere-zero 3-flows in Cayley graphs on solvable groups of twice square-free order, arXiv:2603.24175 (2026), DOI: 10.48550/arXiv.2603.24175, https://arxiv.org/abs/2603.24175
16. C. N. da Silva, C. L. Lucchesi, 3-Flows and Combs, Journal of Graph Theory 77 (2014) 260–277, DOI: 10.1002/jgt.21785, https://doi.org/10.1002/jgt.21785
17. J. Barát, D. Gerbner, Edge-decomposition of graphs into copies of a tree with four edges, The Electronic Journal of Combinatorics 21(1) (2014) #P1.55, DOI: 10.37236/2110, https://doi.org/10.37236/2110
18. J. Bensmail, A. Harutyunyan, T.-N. Le, M. Merker, S. Thomassé, A proof of the Barát–Thomassen conjecture, Journal of Combinatorial Theory, Series B 124 (2017) 39–55, DOI: 10.1016/j.jctb.2016.12.006, https://doi.org/10.1016/j.jctb.2016.12.006
19. M. Hasanvand, Modulo orientations with bounded out-degrees, Discrete Mathematics 347 (2024) 113634, DOI: 10.1016/j.disc.2023.113634, https://doi.org/10.1016/j.disc.2023.113634
20. X. Wang, Y. Lu, Z. Miao, Z3-connectivity of signed graphs with independence number at most two, Discrete Mathematics 349 (2026) 115068, DOI: 10.1016/j.disc.2026.115068, https://doi.org/10.1016/j.disc.2026.115068