pith. sign in

arxiv: 2512.17342 · v3 · submitted 2025-12-19 · 🧮 math.CO · cs.DM

Nowhere-zero flow reconfiguration

Louis Esperet , Kevin Hendrey , Aur\'elie Lagoutte , Margaux Marseloo , Sergey Norin , Raphael Steiner This is my paper

Pith reviewed 2026-05-16 21:13 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords nowhere-zero flowsflow reconfigurationabelian groups2-edge-connected graphsTutte conjectureplanar dualitycycle differences
0
0 comments X

The pith

All nowhere-zero Z_2^8-flows on every 2-edge-connected graph are connected by sequences differing on single cycles.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper initiates the study of reconfiguring nowhere-zero flows on graphs, asking whether any two such flows can be transformed into each other by successively altering the flow values along one cycle while keeping the flow nowhere-zero at every step. It proves that this holds for all flows valued in the group Z_2^8 on any 2-edge-connected graph, and likewise for flows valued in any sufficiently large abelian group. The work also shows that the analogous statement fails for smaller groups and for the natural reconfiguration version of Tutte's 5-flow conjecture, while highlighting a duality that yields results for planar graphs such as the connectivity of nowhere-zero 7-flows.

Core claim

The central claim is that the reconfiguration graph whose vertices are the nowhere-zero A-flows of a 2-edge-connected graph G, with two flows adjacent whenever they differ only on a single cycle of G, is connected whenever A equals Z_2^8 or A is any abelian group whose order is sufficiently large. This connectivity holds independently of the particular graph G, although the group structure itself affects the answer in a way that has no analogue for the mere existence of nowhere-zero flows.

What carries the argument

Nowhere-zero A-flow reconfiguration via single-cycle differences, where two flows are adjacent if their difference is supported on one cycle and the intermediate flows remain nowhere-zero.

If this is right

  • The natural reconfiguration version of Tutte's 5-flow conjecture is false in both the group-flow and integer-flow settings.
  • Any two nowhere-zero 7-flows of a planar graph are connected by a sequence of nowhere-zero 7-flows differing on single cycles.
  • For every 2-edge-connected graph G there exists an integer k such that all nowhere-zero k-flows of G are connected via single-cycle changes.
  • Unlike the existence problem for nowhere-zero flows, the choice of abelian group affects whether reconfiguration is possible.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The duality with planar recoloring suggests that analogous reconfiguration results may hold for proper colorings of planar graphs.
  • The connectivity proofs could be turned into polynomial-time algorithms that explicitly construct reconfiguration sequences for the groups where connectivity is guaranteed.
  • The results raise the question of the smallest group order guaranteeing connectivity for each fixed graph, which may be computable on small instances.

Load-bearing premise

The graphs must be 2-edge-connected so that nowhere-zero flows exist and the stated reconfiguration connectivity can hold.

What would settle it

A single 2-edge-connected graph containing two nowhere-zero Z_2^8-flows with no sequence of nowhere-zero Z_2^8-flows connecting them by single-cycle changes.

Figures

Figures reproduced from arXiv: 2512.17342 by Aur\'elie Lagoutte, Kevin Hendrey, Louis Esperet, Margaux Marseloo, Raphael Steiner, Sergey Norin.

Figure 1
Figure 1. Figure 1: Illustration of a Z4-flow in K4 and the only cycle along which some flow value can be added. is not connected). We will see at the end of Section 4 that this holds more generally for all uniquely 3-edge-colorable cubic planar graphs. We can then compute the reconfiguration graph F(K4, 4) of the nowhere-zero 4- flows of K4, depicted in [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The reconfiguration graph F(G, 4) of nowhere-zero 4-flows in K4. 3. Frozen configurations A typical way to show that the reconfiguration graph C(G, k) defined above for colorings is not connected is to find a proper k-coloring of G where for each vertex v, all the colors distinct from that of v appear in the neighborhood of v. In this case no vertex can be recolored, and the coloring is said to be frozen. … view at source ↗
Figure 3
Figure 3. Figure 3: A 3-edge-connected cubic graph G with a nowhere-zero Z5-flow f having a unique neighbor g in F(G, Z5). The support of g − f is highlighted in bold. The proof of the variant of Theorem 3.2 for integer flows is surprisingly more direct than in the group case, and works for all k ⩾ 2. Theorem 3.4. For any 2-edge-connected graph G and integer k ⩾ 2, if the recon￾figuration graph F(G, k) is non-empty, then it h… view at source ↗
Figure 4
Figure 4. Figure 4: The nowhere-zero Z4-flows of G are in bijection with the nowhere-zero Z4-flows of H. The case where v has outdegree 2 is symmetric. The statement above is clear for G = K4, as this graph has 3 perfect matchings and their complement is a 4-cycle. So we can assume that G was obtained from some Klee-graph H by replacing a vertex v by a triangle v1v2v3. But then observe that the nowhere-zero Z4-flows of G are … view at source ↗
Figure 5
Figure 5. Figure 5: A plane (oriented) graph G and its dual (oriented) graph G∗ . Any proper coloring of G∗ induces a nowhere-zero flow in G. In [13], Tutte established a fundamental result that connects flows and colorings in plane graphs. Theorem 5.1 ([13]). Let G be a 2-edge-connected plane graph. Then G has a nowhere-zero k-flow if and only if its dual graph G∗ has a proper k-coloring. We now explain how colorings can be … view at source ↗
Figure 6
Figure 6. Figure 6: Four graphs G for which F(G, 4) and F(G,Z4) are con￾nected. It would be interesting to understand why F(G, 4) is connected for these graphs, and generate infinite families with this property. Due to the cyclic nature of some of these graphs, there are some natural candidates for such infinite families. We mention another interesting case, the Möbius ladder M12, depicted in [PITH_FULL_IMAGE:figures/full_fi… view at source ↗
Figure 7
Figure 7. Figure 7: Two nowhere-zero Z4-flows in the Möbius ladder M12 that form a connected component of size 2 in F(M12, Z4). As 2 ≡ −2 (mod 4), we omit the orientations of the edges with flow value 2. 7.3. Diameter. It turns out that for each of the four graphs of [PITH_FULL_IMAGE:figures/full_fig_p018_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Three graphs G for which F(G,Z4) has 9 connected com￾ponents. For the left-most one, F(G, Z4) is a perfect matching. Recall that Observation 4.6 gives an infinite family of 3-edge-connected graphs G for which F(G, Z4) is a perfect matching on 6 vertices. It would be interesting to construct a family of 3-edge-connected graphs G with the property that F(G,Z4) is an arbitrarily large perfect matching. 7.5. N… view at source ↗
read the original abstract

We initiate the study of nowhere-zero flow reconfiguration. The natural question is whether any two nowhere-zero $k$-flows of a given graph $G$ are connected by a sequence of nowhere-zero $k$-flows of $G$, such that any two consecutive flows in the sequence differ only on a cycle of $G$. We study this problem in the setting of integer flows and group flows, and prove a number of positive and negative results. * The natural reconfiguration variant of Tutte's 5-flow conjecture, stating that any two nowhere-zero 5-flows in any 2-edge-connected graph are connected, is false in the group and integer cases. * All nowhere-zero $\mathbb{Z}_2^8$-flows of every 2-edge-connected graph are connected and for every sufficiently large abelian group $A$, all nowhere-zero $A$-flows of every 2-edge-connected graph are connected. * The group structure affects the answer, contrary to the existence problem for nowhere-zero flows. * We highlight a duality with recoloring in planar graphs and deduce that any two nowhere-zero 7-flows in a planar graph are connected, among other results. * For every 2-edge-connected graph $G$, there is an integer $k$ such that all nowhere-zero $k$-flows of $G$ are connected.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The manuscript introduces nowhere-zero flow reconfiguration, asking whether any two nowhere-zero k-flows of a graph G can be connected by a sequence where consecutive flows differ only on a single cycle. It disproves the reconfiguration analogue of Tutte's 5-flow conjecture for both integer and group flows. Positive results show that the reconfiguration graph is connected for all nowhere-zero Z_2^8-flows on every 2-edge-connected graph and for all nowhere-zero A-flows when A is a sufficiently large abelian group. The paper also establishes a duality with recoloring problems in planar graphs, yielding that any two nowhere-zero 7-flows on a planar graph are connected, and proves that for every 2-edge-connected graph there exists an integer k such that its nowhere-zero k-flows form a connected reconfiguration graph.

Significance. If the results are correct, this paper makes a substantial contribution by initiating the study of reconfiguration in the context of nowhere-zero flows, a fundamental area in graph theory with connections to coloring and other combinatorial problems. The negative result for 5-flows highlights that reconfiguration can behave differently from existence, even when the group structure is the same. The positive theorems for Z_2^8 and large groups provide concrete, broad connectivity guarantees. The duality with planar recoloring is particularly valuable as it transfers known results from one domain to the other. The general existence of some k for each graph is also noteworthy. These findings are likely to stimulate further work on the topic.

minor comments (4)
  1. The notation for the group Z_2^8 in the abstract and main theorems should be clarified as the elementary abelian 2-group of rank 8 to avoid ambiguity with other possible interpretations.
  2. In the section establishing the duality with recoloring, a short explicit description of the correspondence between flow modifications and color changes would strengthen the deduction that nowhere-zero 7-flows on planar graphs are connected.
  3. The final result on existence of some k for each 2-edge-connected G would benefit from either an explicit bound on k or a sketch of how the group order is chosen to ensure connectivity.
  4. A few additional references to prior work on combinatorial reconfiguration (e.g., coloring reconfiguration) and standard texts on nowhere-zero flows would improve context.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes theorems on connectivity of reconfiguration graphs for nowhere-zero flows in 2-edge-connected graphs, using standard definitions of integer and group flows. The positive results for Z_2^8-flows and large abelian groups, the negative result for 5-flows, and the duality with planar recoloring are presented as independent proofs without any reduction of claims to fitted parameters, self-definitional loops, or load-bearing self-citations. The 2-edge-connectivity assumption is the standard prerequisite for flow existence and is not derived from the results themselves. All steps rely on external graph-theoretic foundations rather than internal construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard domain assumptions from graph theory about flows and connectivity; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption The graph is 2-edge-connected
    Invoked throughout for the flow properties and reconfiguration to be considered, as per standard Tutte flow theory context.

pith-pipeline@v0.9.0 · 5550 in / 1143 out tokens · 27112 ms · 2026-05-16T21:13:45.395009+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    Recoloring planar graphs of girth at least five.SIAM J

    Valentin Bartier, Nicolas Bousquet, Carl Feghali, Marc Heinrich, Benjamin Moore, and Théo Pierron. Recoloring planar graphs of girth at least five.SIAM J. Discrete Math., 37(1):332– 350, 2023

    work page 2023

  2. [2]

    Counting edge-Kempe-equivalence classes for 3-edge- colored cubic graphs.Discrete Math., 325:77–84, 2014

    Sarah-Marie Belcastro and Ruth Haas. Counting edge-Kempe-equivalence classes for 3-edge- colored cubic graphs.Discrete Math., 325:77–84, 2014

    work page 2014

  3. [3]

    Bondy and Miklós Simonovits

    John A. Bondy and Miklós Simonovits. Longest cycles in 3-connected 3-regular graphs.Can. J. Math., 32:987–992, 1980

    work page 1980

  4. [4]

    Bonsma and Luis Cereceda

    Paul S. Bonsma and Luis Cereceda. Finding paths between graph colourings: Pspace- completeness and superpolynomial distances. In Ludek Kucera and Antonín Kucera, editors, Mathematical Foundations of Computer Science 2007, 32nd International Symposium, MFCS 2007, Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings, volume 4708 ofLec- ture Notes ...

    work page 2007

  5. [5]

    Flaxman, Alan M

    Martin Dyer, Abraham D. Flaxman, Alan M. Frieze, and Eric Vigoda. Randomly coloring sparse random graphs with fewer colors than the maximum degree.Random Struct. Algo- rithms, 29(4):450–465, 2006

    work page 2006

  6. [6]

    Geometric coloring theory.Adv

    Steve Fisk. Geometric coloring theory.Adv. Math., 24:298–340, 1977

    work page 1977

  7. [7]

    Kempe equivalence of 4-colourings of some plane triangulations, 2025

    Jan Florek. Kempe equivalence of 4-colourings of some plane triangulations, 2025

    work page 2025

  8. [8]

    Fowler.Unique coloring of planar graphs

    Thomas G. Fowler.Unique coloring of planar graphs. Georgia Institute of Technology, 1998

    work page 1998

  9. [9]

    John P. Georges. Non-hamiltonian bicubic graphs.J. Comb. Theory, Ser. B, 46(1):121–124, 1989

    work page 1989

  10. [10]

    thesis in Graph Theory

    Rikke Marie Langhede.Group Connectivity and Group Coloring: A Ph.D. thesis in Graph Theory. PhD thesis, Technical University of Denmark, 2020

    work page 2020

  11. [11]

    Kempe equivalence of colorings

    Bojan Mohar. Kempe equivalence of colorings. InGraph theory in Paris. Proceedings of a conference, GT04, in memory of Claude Berge, Paris, France, July 2004, pages 287–297. Basel: Birkhäuser, 2007

    work page 2004

  12. [12]

    Paul D. Seymour. Nowhere-zero 6-flows.J. Comb. Theory, Ser. B, 30:130–135, 1981

    work page 1981

  13. [13]

    William T. Tutte. A contribution to the theory of chromatic polynomials.Can. J. Math., 6:80–91, 1954. NOWHERE-ZERO FLOW RECONFIGURATION 21 (L. Esperet) Laboratoire G-SCOP (CNRS, Université Grenoble Alpes), Grenoble, France Email address:louis.esperet@grenoble-inp.fr (A. Lagoutte) Laboratoire G-SCOP (CNRS, Université Grenoble Alpes), Grenoble, France Email...

    work page 1954