Uniform connectivity thresholds for nowhere-zero flow reconfiguration

Reconfiguring a nowhere-zero flow of a graph means transforming it into another such flow by a sequence of cycle moves, each changing the flow values on a single cycle while keeping every intermediate flow nowhere-zero. Esperet, Hendrey, Lagoutte, Marseloo, Norin, and Steiner initiated the study of the resulting reconfiguration graphs $\mathcal{F}(G,k)$ (integer $k$-flows) and $\mathcal{F}(G,A)$ (flows over a finite abelian group $A$), and in revisions of their 2025 preprint answered most of the questions they had originally posed: the reconfiguration analogue of Tutte's 5-flow conjecture is false (a 20-vertex cubic graph carries a frozen, isolated nowhere-zero $\mathbb{Z}_5$-flow, so $\mathcal{F}(G,\mathbb{Z}_5)$ and $\mathcal{F}(G,5)$ are disconnected), while $\mathcal{F}(G,\mathbb{Z}_2^8)$ is connected for every 2-edge-connected graph $G$. The surviving open core, which both this paper and the follow-up by Cranston, Li, Su, Wang, and Xu explicitly list as the main remaining questions, comprises: (1) does there exist a single integer $k$ such that $\mathcal{F}(G,k)$ is connected for every 2-edge-connected graph $G$ (each of $k=3,4,5$ fails on an explicit graph, and for each fixed $G$ some $k(G)$ works, but no uniform $k$ is known)? (2) does connectivity of $\mathcal{F}(G,\mathbb{Z}_k)$ imply connectivity of $\mathcal{F}(G,k)$ — open even for $k=4$, and a positive answer would settle (1) affirmatively since $\mathcal{F}(G,\mathbb{Z}_k)$ is connected for all 2-edge-connected $G$ once $k$ is large enough? (3) for which finite abelian groups $A$ with $|A|\ge 5$ is $\mathcal{F}(G,A)$ connected for every 2-edge-connected $G$ — all groups of order 3, 4, and 5 fail while $\mathbb{Z}_2^8$ (order 256) succeeds, so the minimum order of a group with this property lies between 6 and 256, and by a reduction of Cranston et al. the question has the same answer for 2-edge-connected cubic graphs as for all 2-edge-connected graphs?

Background

A nowhere-zero flow is a classical object in graph theory introduced by Tutte. Fix an arbitrary orientation of the edge set of an undirected graph $G$ (all flows of $G$ are taken with respect to one common fixed orientation); a flow assigns to each edge a value — an integer, or an element of a finite abelian group $A$ — such that conservation holds at every vertex: the total value on edges leaving $v$ equals the total on edges entering $v$. The flow is nowhere-zero if no edge receives the neutral element, and an integer flow is a $k$-flow if all values have absolute value less than $k$. Only graphs without bridges (2-edge-connected graphs, i.e. graphs in which every edge lies on a cycle) can carry nowhere-zero flows. Tutte's famous 5-flow conjecture predicts that every 2-edge-connected graph has a nowhere-zero 5-flow; the best partial result, Seymour's 6-flow theorem, gives a nowhere-zero 6-flow (equivalently, by a theorem of Tutte, a nowhere-zero flow over every abelian group of order at least 6). A fundamental theorem of Tutte also shows that the existence of nowhere-zero $A$-flows depends only on the cardinality of $A$, not on its structure. Combinatorial reconfiguration studies the space of solutions of a problem through its reconfiguration graph: vertices are solutions, and two solutions are adjacent when one is obtained from the other by an elementary move. Esperet et al. initiated the reconfiguration study of nowhere-zero flows: the vertices of $\mathcal{F}(G,A)$ (resp. $\mathcal{F}(G,k)$) are the nowhere-zero $A$-flows (resp. $k$-flows) of $G$, and two flows are adjacent when they differ only on a cycle, i.e. when one is obtained from the other by adding a constant along a cycle (an empty reconfiguration graph counts as connected). Connectedness is the basic question — it asks whether the whole flow space can be explored by local cycle moves, which governs whether simple random-sampling dynamics over flows can be ergodic. In their 2025 preprint (arXiv:2512.17342), revised through July 2026, Esperet et al. proved a mixture of positive and negative results. On the negative side, the standard reconfiguration technique of frozen configurations (isolated vertices of the reconfiguration graph) behaves unexpectedly: frozen configurations never exist in $\mathcal{F}(G,A)$ when $|A|=4$ or $|A|\ge 6$, nor in $\mathcal{F}(G,k)$ for any $k\ge 2$, yet $\mathcal{F}(G,\mathbb{Z}_5)$ can have isolated vertices. With the help of Y. Wigderson, P. Morawski, and the automated discovery tool AlphaEvolve they found a 20-vertex 3-connected cubic graph (cubic means all vertices have degree 3) carrying a frozen nowhere-zero $\mathbb{Z}_5$-flow; since a connected $\mathcal{F}(G,k)$ maps onto a connected $\mathcal{F}(G,\mathbb{Z}_k)$ under reduction modulo $k$ (reconfiguration steps map to reconfiguration steps), this single example refutes the reconfiguration analogue of Tutte's 5-flow conjecture in both the group form ($\mathbb{Z}_5$) and the integer form ($k=5$). Group structure matters for reconfiguration, in contrast to existence: $\mathcal{F}(K_4,\mathbb{Z}_2\times\mathbb{Z}_2)$ is connected while $\mathcal{F}(K_4,\mathbb{Z}_4)$ is a perfect matching and hence disconnected. On the positive side, their main theorem (Theorem 6.15) proves $\mathcal{F}(G,\mathbb{Z}_2^8)$ connected for every 2-edge-connected $G$, via composite flows (flows whose components along a product decomposition of the group are themselves nowhere-zero); this extends to every abelian group of order at least $(56^8\cdot 27+28)^{45}+1$ (about $10^{694}$). For planar graphs they establish a duality with graph recoloring and deduce that $\mathcal{F}(G,k)$ and $\mathcal{F}(G,A)$ are connected for all $k\ge 7$ and all $|A|\ge 7$. For every fixed 2-edge-connected $G$ there is an integer $k$ (of order $e(G)\cdot v(G)$) with $\mathcal{F}(G,k)$ connected — but $k$ depends on $G$, and no integer $k\le 5$ works uniformly. The follow-up by Cranston, Li, Su, Wang, and Xu (arXiv:2606.24685) advanced the group side: they characterized the graphs that are $\mathbb{Z}_3$-flow-connected (equivalently 3-flow-connected) as the Eulerian graphs (all degrees even) in which any two vertices are joined by at most 4 edge-disjoint paths; they proved that for every abelian group $A$, all 2-edge-connected graphs are $A$-flow-connected if and only if all 2-edge-connected cubic graphs are; they proved every cubic bipartite graph is 4-flow-connected, every Eulerian graph is $2k$-flow-connected for every $k$ (conjecturing $A$-flow-connectedness whenever $|A|\ge 4$), and every 4-edge-connected graph is $A$-flow-connected whenever $|A|\ge 5{,}251{,}339$. They also settled the small groups: every abelian group of order 3, 4, or 5 fails on some 2-edge-connected graph ($\mathbb{Z}_4$ on $K_4$ and the Klee graphs; $\mathbb{Z}_2\times\mathbb{Z}_2$ on cubic graphs with many Kempe-equivalence classes of 3-edge-colorings, constructed by Belcastro and Haas — for cubic graphs, $\mathbb{Z}_2\times\mathbb{Z}_2$-flow reconfiguration is exactly the classical question whether all 3-edge-colorings of a cubic graph are equivalent under Kempe changes, i.e. swaps of two colors on a connected piece of a two-color subgraph). The group $\mathbb{Z}_2$ is degenerate (every graph has at most one nowhere-zero $\mathbb{Z}_2$-flow), so the meaningful range for the group question is $|A|\ge 5$, the range of Tutte's conjectures, where Seymour's theorem already guarantees that flows exist. What no work resolves are the three linked threshold questions stated below; both papers name them as the main open problems of the area, and the December 2025 version of the source paper posed them as its Conjecture 1.2, Problem 2.4, and (in weaker or stronger forms) Conjectures 1.1, 1.3, 1.4, Problem 6.7, and Conjecture 7.1.

Problem Statement

The problem is the surviving core of the open-question bundle posed by Esperet et al. in December 2025, after their own revisions (v2-v4, 2026) and the follow-up of Cranston et al. resolved or refuted the remaining items. It has one scientific objective — determine the uniform connectivity thresholds of nowhere-zero flow reconfiguration graphs over the class of 2-edge-connected graphs — expressed as three linked questions, where throughout $\mathcal{F}(G,k)$ (resp. $\mathcal{F}(G,A)$) denotes the reconfiguration graph of nowhere-zero $k$-flows (resp. $A$-flows over a finite abelian group $A$) of $G$, with two flows adjacent when they differ only on a cycle. (Q1, integer threshold — Problem 1.2 of Esperet et al. (v4 revision; Conjecture 1.2 in the December 2025 version)) Does there exist an integer $k$ such that $\mathcal{F}(G,k)$ is connected for every 2-edge-connected graph $G$? Each of $k=3,4,5$ fails on an explicit 2-edge-connected graph, and for every fixed $G$ some $k(G)$ (of order $e(G)\cdot v(G)$) works, but no bound independent of $G$ is known; a negative answer would be a construction showing that for every integer $k$ there is a 2-edge-connected graph $G$ with $\mathcal{F}(G,k)$ disconnected. (Q2, integer-group bridge — Problem 2.6 of Esperet et al. (v4 revision; Problem 2.4 in the December 2025 version), Conjecture A of Cranston et al.) Is it true for every graph $G$ and every integer $k\ge 2$ that if $\mathcal{F}(G,\mathbb{Z}_k)$ is connected then $\mathcal{F}(G,k)$ is connected? The converse implication is proven; this direction is open even for $k=4$. By the large-group theorem, $\mathcal{F}(G,\mathbb{Z}_k)$ is connected for every 2-edge-connected $G$ whenever $k\ge(56^8\cdot 27+28)^{45}+1$, so a positive answer to Q2 would give a positive answer to Q1. (Q3, group threshold) For which finite abelian groups $A$ with $|A|\ge 5$ is $\mathcal{F}(G,A)$ connected for every 2-edge-connected graph $G$? The goal is a characterization of the groups with this uniform connectivity property: since connectivity depends on the group structure at a fixed order (as $\mathbb{Z}_2\times\mathbb{Z}_2$ versus $\mathbb{Z}_4$ on $K_4$ shows), knowing the minimum order alone would not determine which groups work. All groups of order 3, 4, and 5 fail, and $\mathbb{Z}_2^8$ (order 256) succeeds, so the minimum order of a group with this property lies between 6 and 256; in particular, it is open whether $\mathbb{Z}_6$ (the smallest order for which Seymour's theorem guarantees that every 2-edge-connected graph carries a nowhere-zero flow) already works. By a reduction of Cranston et al., for every finite abelian group $A$, $\mathcal{F}(G,A)$ is connected for every 2-edge-connected graph $G$ if and only if it is connected for every 2-edge-connected cubic graph $G$. These three questions are independently refutable sub-claims of the single objective above: a decisive answer to each settles that sub-claim, the objective is complete once all three are settled, and, as noted under Q2, a positive answer to Q2 settles Q1 as well.

References

1. Louis Esperet, Kevin Hendrey, Aurélie Lagoutte, Margaux Marseloo, Sergey Norin, and Raphael Steiner, "Nowhere-zero flow reconfiguration", arXiv:2512.17342 (v1 December 2025; v4 revised 3 July 2026), https://arxiv.org/abs/2512.17342
2. Daniel W. Cranston, Jiaao Li, Bo Su, Zhouningxin Wang, and Ningyan Xu, "Reconfiguration of Nowhere-zero Flows", arXiv:2606.24685 (June 2026), https://arxiv.org/abs/2606.24685
3. W. T. Tutte, "A contribution to the theory of chromatic polynomials", Canadian Journal of Mathematics 6 (1954) 80-91, DOI 10.4153/cjm-1954-010-9, https://doi.org/10.4153/cjm-1954-010-9
4. P. D. Seymour, "Nowhere-zero 6-flows", Journal of Combinatorial Theory, Series B 30 (1981) 130-135, DOI 10.1016/0095-8956(81)90058-7, https://doi.org/10.1016/0095-8956(81)90058-7
5. Sarah-Marie Belcastro and Ruth Haas, "Counting edge-Kempe-equivalence classes for 3-edge-colored cubic graphs", Discrete Mathematics 325 (2014) 77-84, DOI 10.1016/j.disc.2014.02.014, https://doi.org/10.1016/j.disc.2014.02.014