betaFeedback

WorksMathematics

Integer and modular flow reconfiguration: the moduli up to six, chords, and large moduli

Abstract

For a finite multigraph GG and an integer k≥2k\ge2, let Mk(G)\mathcal M_k(G) be the graph on the nowhere-zero Zk\mathbb Z_k-flows of GG, and Ik(G)\mathcal I_k(G) the graph on the integer flows FF of GG with 1≤∣F(e)∣≤k−11\le|F(e)|\le k-1 on every edge; a step adds a nonzero constant along one cycle. The Esperet–Hendrey–Lagoutte–Marseloo–Norin–Steiner (2025) lifting question asks for a proof that Ik(G)\mathcal I_k(G) is connected whenever Mk(G)\mathcal M_k(G) is connected; its authors write that they do not know how to prove this even for k=4k=4. We prove it for k=2,3,4,5,6k=2,3,4,5,6 and every graph, in a stronger form: reduction modulo kk induces a bijection between the components of Ik(G)\mathcal I_k(G) and of Mk(G)\mathcal M_k(G). We prove the same for every kk on the graphs in which every cycle with more than nine edges has a chord between two vertices that are not neighbors on the cycle. We also prove that Ik(G)\mathcal I_k(G) is connected for every bridgeless multigraph GG and every k≥mc⁡(G)+2k\ge\operatorname{mc}(G)+2, where mc⁡(G)\operatorname{mc}(G) is the largest number of edges of a cut of GG; and that scaling by mm carries the components of Mk(G)\mathcal M_k(G) into components of Imk(G)\mathcal I_{mk}(G). With a theorem of Esperet et al. on planar graphs, the first result settles the question for every planar graph and every kk. The bijection of the components for k≤6k\le6 holds more generally for the integer and modular kernel vectors of every totally unimodular matrix, with the circuit vectors as steps, and in this generality it fails at every prime p≥7p\ge7, for the tensions of a graph on 2p2p vertices; this does not answer the question for the flows of graphs. For the six moduli k=8,9,12,16,18,36k=8,9,12,16,18,36 we prove the bijection of the components for every graph also; this is a short deduction from a lemma on liftable steps of a companion paper. For the other k≥7k\ge7 this paper does not settle the question on arbitrary graphs.

Introduction

Graphs are finite multigraphs; loops and parallel edges are allowed. Let k≥2k \ge2 be an integer. A modular flow is a nowhere-zero Zk\mathbb{Z}_k-flow of GG, and an integer kk-flow is an integer circulation FF with 1≤∣F(e)∣≤k−11 \le|F(e)| \le k - 1 on every edge. A step adds a nonzero constant along one cycle, and it is legal if the result is again a flow of the same kind. Mk(G)\mathcal{M}_k(G) is the graph on the modular flows and Ik(G)\mathcal{I}_k(G) the graph on the integer kk-flows, with the legal steps as edges. These are the graphs F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) and F(G,k)\mathcal{F}(G,k) of Esperet, Hendrey, Lagoutte, Marseloo, Norin and Steiner [1]. The exact definitions are in Section 2, for the second part of the paper in Section 7, and for matrices in Section 12.

The lifting question

Reduction modulo kk maps integer kk-flows onto modular flows, and an integer step to a modular step or to equality. So, if Ik(G)\mathcal{I}_k(G) is connected, then Mk(G)\mathcal{M}_k(G) is connected; this is Observation 2.5 of [1]. The converse is the Esperet–Hendrey–Lagoutte–Marseloo–Norin–Steiner (2025) lifting question, their Problem 2.6:

“Let GG be a graph and kk be an integer. Prove that if F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) is connected, then F(G,k)\mathcal{F}(G,k) is also connected.” They write directly after it: “We do not know how to prove the result even in the case k=4k = 4.” Cranston, Li, Su, Wang and Xu state the equivalence of the two connectivity properties as a conjecture [2 Conjecture A].

The results

Theorem 1.1. Let GG be a finite multigraph, and let k≥2k \ge2 be an integer.

(a) If k≤6k \le6, then reduction modulo kk induces a bijection between the connected components of Ik(G)\mathcal{I}_k(G) and of Mk(G)\mathcal{M}_k(G).

(b) Suppose that every cycle of GG with more than nine edges has an edge outside the cycle joining two distinct vertices that are not neighbors on the cycle. Then the conclusion of (a) holds for every k≥2k \ge2. For k=7k = 7 it holds with nine replaced by twenty-one.

(c) If GG is bridgeless and k≥mc⁡(G)+2k \ge\operatorname{mc}(G) + 2, where mc⁡(G)\operatorname{mc}(G) is the largest number of edges of a cut of GG, then Ik(G)\mathcal{I}_k(G) is connected.

Part (a) is Theorem 2.1, part (b) is Theorem 2.2, and part (c) is Theorem 7.1. In the cases (a) and (b), Ik(G)\mathcal{I}_k(G) is connected if and only if Mk(G)\mathcal{M}_k(G) is connected; so the implication of the lifting question holds there, for k=4k = 4 in particular. The statement on the components says more: Mk(G)\mathcal{M}_k(G) need not be connected (for six parallel edges and k=3k = 3 it is not [2 Theorem 2.1]), and then Ik(G)\mathcal{I}_k(G) has exactly as many components, and reduction modulo kk matches them. In case (c) the graph Mk(G)\mathcal{M}_k(G) is connected as well, by reduction and lifting (Lemma 3.2); so for these pairs (G,k)(G,k) both graphs are connected. For simple graphs the hypothesis of (b) says that no induced cycle has more than nine edges.

For planar graphs, part (a) and a theorem of [1] leave no modulus open.

Corollary 1.2. Let GG be a planar multigraph, and let k≥2k \ge2 be an integer. Then Ik(G)\mathcal{I}_k(G) is connected if and only if Mk(G)\mathcal{M}_k(G) is connected.

Proof. For k≤6k \le6 this follows from Theorem 1.1 (a). Let k≥7k \ge7; we show that both graphs are connected. As in § 2, a reconfiguration graph with at most one vertex is regarded as connected. If GG has a bridge, then GG has no flow of either kind, and both graphs are empty. Suppose that GG is bridgeless. A loop is a cycle, and a step on it changes the value of this loop only, to any other allowed value; and every cycle that is not a loop lies in one component of GG. So each of Ik(G)\mathcal{I}_k(G) and Mk(G)\mathcal{M}_k(G) is the Cartesian product of the corresponding graphs of the components of the graph GG without its loops, and of one complete graph for each loop. A component without an edge has one flow of each kind, the empty map. Every other component is a 2-edge-connected loopless planar graph, and its two reconfiguration graphs are connected by [1 Corollary 5.9]. A finite product of nonempty connected graphs is connected, and a product with an empty factor is empty. □\square

For k≥7k \ge7 we prove the statement of the lifting question on arbitrary graphs only at the six moduli 8, 9, 12, 16, 18 and 36 (Theorem 18.1; see “Six more moduli” below). For the other k≥7k \ge7 this paper does not settle it on arbitrary graphs; by Corollary 1.2, a graph for which it is not settled here is not planar. The smallest such modulus is k=7k = 7: by Corollary 4.2 and Theorem 2.3, the only modular steps that are not treated there have size 3 or 4 and lie on cycles with at least twenty-two edges. That this paper does not settle a modulus does not mean that it is open: at k=40k = 40, at k=48k = 48 and at every multiple kk of 4 with k≥52k \ge52 the earlier paper [4] proves that both graphs of flows are connected for every graph with no bridge and no loop (see “What was known, and two companion papers” below).

Six more moduli

Six more moduli. For k=8,9,12,16,18,36k=8,9,12,16,18,36 the conclusion of part (a) of Theorem 1.1 holds for every graph: this is Theorem 18.1. Its proof, in § 18 to § 20, is a short deduction from a lemma of the earlier paper [4] on the steps that can be lifted (its Lemma 1.12): at each of the six moduli, every element other than 0 is one of the elements that the lemma names. The six moduli were found in the work on that paper and are not stated in it. § 17 names the four statements of [4 Section 1] that the proof uses; their proofs are there. Corollary 18.2 applies the theorem, with two results of the companion paper [5] on the Zk\mathbb{Z}_k-flows, to the graphs in which every connected component has at most eight, at most twelve, or at most twenty-four vertices of odd degree. The theorem and the corollary make no statement on any other modulus k≥7k \ge7, and we give no classification of the moduli for which this deduction works; the modulus 7 is not one of them (Remark 20.1).

Totally unimodular matrices

Totally unimodular matrices. Part (a) of Theorem 1.1 is not special to graphs. Let AA be a finite integer matrix with column set EE that is totally unimodular: each square subdeterminant is 0, 1 or −1-1. An integer kk-flow of AA is a vector F∈ZEF \in\mathbb{Z}^{E} with AF=0AF=0 and $1 \le |F_e| \le k-1$ for every ee, and a modular kk-flow of AA is a vector f∈(Zk)Ef \in(\mathbb{Z}_k)^{E} with Af=0Af=0 in Zk\mathbb{Z}_k and fe≠0f_e \ne0 for every ee. A circuit vector is an integer vector in the kernel of AA whose support is not empty and is minimal among the supports of the nonzero real kernel vectors, and whose nonzero entries have greatest common divisor one; its entries are 0, 1 and −1-1 (Lemma 13.2). A step adds a nonzero multiple of a circuit vector. Ik(A)\mathcal{I}_k(A) and Mk(A)\mathcal{M}_k(A) are the graphs on the integer and on the modular kk-flows of $A, with the legal steps as edges. The exact definitions are in § 12.

Theorem 1.3. The following two statements hold.

(a) For every totally unimodular matrix AA and every k∈{2,3,4,5,6}k \in\{2,3,4,5,6\}, reduction modulo kk induces a bijection between the connected components of Ik(A)\mathcal{I}_k(A) and of Mk(A)\mathcal{M}_k(A).

(b) For every prime p≥7p \ge7 there is a totally unimodular matrix AA, representing the tension space of a finite simple graph, for which reduction modulo pp does not induce an injection on connected components: a component of Mp(A)\mathcal{M}_p(A) with two vertices has lifts in at least two different components of Ip(A)\mathcal{I}_p(A).

Part (a) is Theorem 12.1, and part (b) is Theorem 12.2. The integer kernels of totally unimodular matrices are regular chain groups in the sense of Tutte [6]. If AA is the oriented incidence matrix of a graph GG, then the flows of AA are the flows of GG and the circuit vectors are the signed indicator vectors of the cycles of GG; so for graphs part (a) is Theorem 1.1 (a) again. Its proof in § 12 to § 14 is shorter than the proof in § 3 to § 6: it rounds a real vector directly and uses no cut condition and no count of intervals. This shorter proof is not new for graphs: it is the proof by the lemmas of [4], carried over to matrices (see “Relation to our earlier paper” below).

Part (b) refutes the bijection of the components in the wider setting; it does not refute the implication of the lifting question, and it is not a statement on the flows of a graph. Its matrices represent tensions, the vectors of the differences of a vertex potential along the edges, of a graph HpH_p that consists of two complete graphs on pp vertices and of p(p−2)p(p-2) edges between them. This graph contains K5K_5, so its tension space is not the flow space of a graph (see the remark at the end of § 16); and the graph Mp(A)\mathcal{M}_p(A) of the example is not connected, so the example does not even contradict the statement “if Mp(A)\mathcal{M}_p(A) is connected, then Ip(A)\mathcal{I}_p(A) is connected”. What it shows is that a proof of the bijection of the components for the flows of all graphs at a prime p≥7p \ge7 cannot be a proof for all totally unimodular matrices. Theorem 1.3 claims nothing for composite moduli above six, and nothing for the flows of graphs at k=7k=7.

What was known, and two companion papers

Esperet et al. [1 Theorem 7.1] prove that F(G,k)\mathcal{F}(G,k) is connected at some modulus kk for each loopless 2-edge-connected graph GG; the modulus chosen in their proof is 36∣E(G)∣(∣V(G)∣+1)36\lvert E(G)\rvert(\lvert V(G)\rvert+1). For planar graphs they prove more [1 Corollary 5.9]: for every 2-edge-connected planar graph GG, every integer k≥7k \ge7 and every abelian group AA with at least seven elements, the graphs F(G,k)\mathcal{F}(G,k) and F(G,A)\mathcal{F}(G,A) are connected. So the lifting question was answered for these pairs (G,k)(G,k); their Corollaries 5.10 to 5.12 lower the bound 7 for planar graphs of higher edge-connectivity and for outerplanar graphs. The graphs of [1] may have multiple edges, but no loop.

The paper [4] proves that Mk(G)\mathcal{M}_k(G) and Ik(G)\mathcal{I}_k(G) are both connected for every finite bridgeless loopless multigraph GG if k=40k=40, if k=48k=48, or if kk is a multiple of 4 with k≥52k \ge52 [4 Theorem 9.2]. For one fixed graph GG it gives every modulus from a bound on: every k≥max⁡(48,c(G)+4)k \ge\max(48,c(G)+4), where c(G)c(G) is the number of edges of a longest cycle of GG, and every k≥40k \ge40 if c(G)≤39c(G) \le39 [4 Corollary 10.6]; every k≥40k \ge40 if GG has at most 189 edges [4 Corollary 10.12] or at most 149 vertices [4 Corollary 10.16]. It claims nothing for a modulus below 40 on all graphs, and nothing for a prime modulus on all graphs; but some statements of the present paper follow from its lemmas, and we say which under “Relation to our earlier paper” below.

The paper [5] proves the Cranston–Li–Su–Wang–Xu (2026) conjecture [2 Conjecture 4.1] for the integer flows: both graphs are connected for every graph with all degrees even and every k≥4k \ge4; and that the implication of the lifting question holds for these graphs for every k≥2k \ge2.

Part (c) of Theorem 1.1 is a bound of the same kind as the bound max⁡(48,c(G)+4)\max(48,c(G)+4) of [4], with another parameter, and neither contains the other. For the complete graph K4K_4 we have mc⁡(K4)=4\operatorname{mc}(K_4)=4, so (c) gives every k≥6k \ge6, and [4] gives every k≥40k \ge40. For the complete bipartite graph K3,nK_{3,n} with n≥3n \ge3 we have c=6c=6 and mc⁡=3n\operatorname{mc}=3n, so [4] gives every k≥40k \ge40, and (c) gives every k≥3n+2k \ge3n+2. The proof of (c) uses no base modulus: it uses Hoffman’s circulation theorem and a walk through the regions of a hyperplane arrangement.

More results

  1. Every legal modular step on a cycle with at most nine edges has two adjacent integer lifts, for every k≥3k \ge3; for k=7k=7 the same holds for at most twenty-one edges (Theorem 2.3).

  2. For every k≥3k \ge3, every legal modular step of size 1, −1-1, 2 or −2-2 has a pair of adjacent integer lifts (Corollary 4.2).

  3. For k=2dk=2d with d≥2d \ge2 and a legal modular step of size dd, all integer lifts of both endpoints lie in one component of Ik(G)\mathcal{I}_k(G) (Lemma 5.1).

  4. Scaling: if two modular flows lie in one component of Mk(G)\mathcal{M}_k(G) and FF, F′F' are integer kk-lifts of them, then mFmF and mF′mF' lie in one component of Imk(G)\mathcal{I}_{mk}(G), for every m≥2m \ge2 (Theorem 11.1).

  5. If GG is connected and bridgeless and {e,f}\{e,f\} is a cut of GG, then Ik(G)\mathcal{I}_k(G) and Ik(G/e)\mathcal{I}_k(G/e) are isomorphic (Lemma 10.1).

Relation to our earlier paper

Several statements of this paper follow from lemmas of the paper [4], which treats loopless multigraphs, or were obtained together with it. We say here which, so that nothing old is read as new.

Part (a) of Theorem 1.1. For every k≥3k \ge3, [4 Lemma 1.12 (a)–(d)] states that all integer lifts of one modular flow lie in one component of Ik(G)\mathcal{I}_k(G), and that for a legal modular step of size ±1\pm1, of size ±2\pm2, or of size ±q\pm q for a divisor qq of kk with 1≤q<k1 \le q < k, all integer lifts of its two endpoints lie in one component. For 3≤k≤63 \le k \le6 every nonzero residue is of one of these three kinds. For k=2k=2 there is at most one modular flow, and its integer lifts lie in one component by [4 Corollary 1.3 and Lemma 1.4]. So part (a) follows from these lemmas for loopless multigraphs. The paper [4] does not state part (a) and does not name its consequence for the lifting question. This paper adds to part (a) the statement with that consequence, loops, and another proof, by cut conditions and a count of intervals (Sections 3 to 6).

Theorem 18.1 and Section 17. The theorem is a deduction from [4 Lemma 1.12 (a)–(e)]; part (e) of that lemma is used in this paper for this theorem only. Section 17 names the four statements of Section 1 of [4] that the theorem uses, with their numbers there; it gives no proofs.

Results (ii), (iii) and (v). For loopless multigraphs, result (ii) is [4 Lemmas 1.8 and 1.9]; the proof of Lemma 1.9 there rounds the vector (r+χC)/k(r + \chi_C)/k, as the proof of Lemma 14.1 does here for matrices. Result (iii) is the case q=k/2q = k/2 of [4 Lemma 1.12 (d)]. The contraction of an edge of a cut with two edges, result (v), is used for flows with values in a group in the proof of the master theorem of [4 Section 3]; here it is stated as an isomorphism of the graphs on the integer flows.

What is new in this paper. Part (b) of Theorem 1.1 in its form for all kk, which puts together the result (i) on short cycles and the chord lemma (Lemma 6.1); part (c), which is compared with the bound of [4] above; and the scaling statement (iv), whose proof uses the lemmas on the steps of size 1 and 2 again.

The other statements. Corollary 1.2, both parts of Theorem 1.3 and result (i) are not in [4]. They were obtained together with that paper, and they are written up here for the first time; the case k=7k = 7 of part (b) follows at once from what was obtained then.

The proofs in a few lines

Small moduli and chords (Sections 2 to 6). Every modular flow has integer lifts, and all of them lie in one component of Ik(G)I_k(G) (Lemma 3.2). So it is enough to show, for one legal modular step f→f+cχCf \to f + c\chi_C, that some lift of ff and some lift of f+cχCf + c\chi_C lie in one component. A pair of adjacent lifts whose difference lies on CC exists if and only if one of two cut conditions of Hoffman type holds (Lemma 3.3). A cut that violates such a condition meets the cycle CC in many intervals, and this needs many edges of CC (Lemma 4.1). So steps of size ±1\pm1, ±2\pm2 always have adjacent lifts, and so has every step on a short cycle. For k≤5k \le5 there is no other size. For k=6k = 6 the size 3 is treated by a path through other modular flows (Lemma 5.1). A chord between two vertices that are not neighbors on CC splits a step on CC into two steps of the same size on shorter cycles, unless 2c=02c = 0 modulo kk (Lemma 6.1); the case 2c=02c = 0 is the step of size k/2k/2 of Lemma 5.1. This gives (b) by induction on the length of the cycle.

Large moduli (Sections 7 to 10). All integer kk-flows that are positive on the same orientation lie in one component (Lemma 8.1). If two strong orientations differ on one edge and k≥mc⁡(G)+2k \ge\operatorname{mc}(G) + 2, then Hoffman’s theorem gives two adjacent integer kk-flows, one for each orientation (Lemma 8.2). In a 3-edge-connected graph the strong orientations are the regions of the arrangement of the hyperplanes z(e)=0z(e) = 0 in the space of real circulations, and a segment in general position joins two regions by crossing one hyperplane at a time (Lemma 9.1). Loops and cuts with two edges are removed first (Lemma 10.1).

Scaling (Section 11). For a modular step f→f+cχCf \to f + c\chi_C with 1≤c≤k−11 \le c \le k - 1, the maps mf+sχCmf + s\chi_C are nowhere zero modulo mkmk for s=0s = 0, for s=mcs = mc, and for every ss between them that mm does not divide. Consecutive ones differ by a step of size 1 or 2, and such steps have adjacent integer lifts (Lemma 11.4).

Totally unimodular matrices (Sections 12 to 16). If x∈[0,1]Ex \in[0,1]^E and AxAx is integral, then there is z∈{0,1}Ez \in\{0,1\}^E with Az=AxAz = Ax that agrees with xx wherever xx is integral (Lemma 13.1). This gives the integer lifts of a modular flow, and a lift that takes a given step of size $\pm 1 or ±2\pm2 (Lemmas 13.3 and 14.1); the step of size dd for k=2dk = 2d is treated as in the first part (Lemma 14.2). For part (b) of Theorem 1.3, a nowhere-zero tension modulo pp is a proper colouring with pp colours up to a constant, and a step shifts the colours on one side of a minimal cut by a constant (Lemma 15.1). In HpH_p each of the two complete graphs has all pp colours and pp is prime, so a step shifts each of them as a whole or not at all. The component of the colouring cc of the example has two vertices, cc and the colouring with the first complete graph shifted by 3. An integer step between lifts of these two would shift the first complete graph, up to a constant on all vertices, by an integer b≡3b \equiv3 modulo pp with ∣b∣≤2p−2|b| \le2p - 2; each of the four such values is excluded by the bounds on the edges between the two complete graphs.

The parts, and the notation

Sections 2 to 6, Sections 7 to 11 and Sections 12 to 16 can be read independently, and each part states its definitions. Section 17 and the three sections after it are a fourth part: Section 17 names the statements of [4] that this part uses, and the three sections after it quote them in their own words. The proof of Theorem 18.1 uses these statements only; Corollary 18.2 also uses the two results of the companion paper [5] that it cites. Sections 18 to 20 write F(G,k)\mathcal{F}(G, k) and F(G,Zk)\mathcal{F}(G, \mathbb{Z}_k). The first part writes Ik(G)\mathcal{I}_k(G) and Mk(G)\mathcal{M}_k(G); the second part writes F(G,k)\mathcal{F}(G, k) and F(G,Zk)\mathcal{F}(G, \mathbb{Z}_k) for the same two graphs, as [1] does. Two lemmas are stated and proved in both of these parts: Lemma 11.2 is Lemma 3.1, and Lemma 11.3 is the first sentence of Lemma 3.2. Hoffman’s theorem is stated in the form with supplies and demands in Section 3, and in the form for circulations in Section 8. The third part writes Ik(A)\mathcal{I}_k(A) and Mk(A)\mathcal{M}_k(A) for a matrix AA, and all its labels of theorems and lemmas are its own. For the oriented incidence matrix of a graph, its Lemmas 13.1, 13.3 and 14.2 are Lemmas 3.1, 3.2 and 5.1 of the first part.

Definitions and statements

Graphs are finite multigraphs, with loops and parallel edges allowed. A cycle is a connected 2-regular subgraph, including a loop or two parallel edges. Give each edge a reference direction. For a cycle CC with a direction of traversal, χC\chi_C is 1 on edges traversed forward, −1-1 on edges traversed backward, and 0 elsewhere. The divergence of a map on edges is its outgoing sum minus its incoming sum at each vertex; a loop cancels in this sum.

For k≥2k \ge2, a Zk\mathbb{Z}_k-flow is an edge map with divergence zero in Zk\mathbb{Z}_k; a modular flow will mean a nowhere-zero Zk\mathbb{Z}_k-flow. A circulation has divergence zero at every vertex. An integer kk-flow is an integer circulation FF with 1≤∣F(e)∣≤k−11 \le|F(e)| \le k - 1 on every edge. Their reconfiguration graphs are Mk(G)\mathcal{M}_k(G) and Ik(G)\mathcal{I}_k(G): a step adds a nonzero constant times χC\chi_C, and both endpoints must be flows of the specified kind. An integer lift of a modular flow has the same edge values modulo kk. Reduction modulo kk maps an integer step to a modular step or to equality. A reconfiguration graph with at most one vertex is regarded as connected. Our Ik(G)\mathcal{I}_k(G) and Mk(G)\mathcal{M}_k(G) are the graphs F(G,k)\mathcal{F}(G,k) and F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) of [1]. That paper treats loopless graphs; here loops are allowed.

The lifting question of Esperet et al. [1 Problem 2.6] asks for a proof that connectivity of Mk(G)\mathcal{M}_k(G) implies connectivity of Ik(G)\mathcal{I}_k(G). They state their belief in this implication and write immediately after the question: “We do not know how to prove the result even in the case k=4k = 4.” Cranston et al. state as a conjecture [2 Conjecture A] the equivalence of the two connectivity properties; the reverse implication follows by reduction and lifting. We prove the stronger component correspondence for small moduli on all graphs, and for every modulus on the following structural classes.

A direct integer lift of a modular step f→f+cχCf \to f + c\chi_C is a pair of adjacent integer lifts, one of ff and one of f+cχCf + c\chi_C, whose difference is supported on CC. We say that a lift FF accepts an integer increment aa on CC if F+aχCF+a\chi_C is an integer kk-flow. A cc-step means a modular step with increment cc.

Theorem 2.1. For every finite multigraph GG and every k∈{2,3,4,5,6}k \in\{2,3,4,5,6\}, reduction modulo kk induces a bijection between the connected components of Ik(G)I_k(G) and Mk(G)M_k(G).

Theorem 2.2. Suppose every cycle of GG with more than nine edges has an edge outside the cycle joining two distinct vertices that are not neighbors on the cycle. Then, for every k≥2k \ge2, reduction modulo kk induces a bijection between the connected components of Ik(G)I_k(G) and Mk(G)M_k(G). For k=7k=7, the same conclusion holds with nine replaced by twenty-one.

For simple graphs the hypothesis says that no induced cycle is longer than the stated bound: a cycle is induced exactly when it has no edge joining two of its nonneighboring vertices. The explicit nonneighbor-chord condition also applies to multigraphs. An additional edge parallel to a cycle edge does not provide the strict shortening used below.

Theorem 2.3. Every legal modular step on a cycle of length at most nine has two adjacent integer lifts, for every k≥3k \ge3. For k=7k=7, the same holds for length at most twenty-one.

Our proof for k=6k=6 treats increment 3 by a path between the lifting fibres, without requiring a direct integer lift of that step. For k≥7k \ge7, the results of Sections 2 to 6 do not assert the conjecture for arbitrary graphs; the six composite moduli 8, 9, 12, 16, 18, 36 are treated in Theorem 18.1.

Lifting facts and prescribed signs

We include proofs of the lifting facts used below. A possibly-zero Zk\mathbb{Z}_k-flow may be lifted with its zero edges kept zero.

Lemma 3.1 (rounding). If x:E(G)→[0,1]x : E(G) \to[0,1] has integral divergence, there is z:E(G)→{0,1}z : E(G) \to\{0,1\} with the same divergence and with z(e)=x(e)z(e)=x(e) wherever x(e)x(e) is integral.

Proof. The fractional edges, if nonempty, contain a cycle. A fractional loop is already a cycle; otherwise a vertex cannot have just one incident fractional edge, by integral divergence. Choose a cycle of fractional edges and one direction of traversal. Add a positive multiple of its vector χC\chi_C, as far as possible while staying in [0,1][0,1]. At least one fractional coordinate becomes integral, and no integral coordinate changes. Repeat until none is fractional. □

The lifting and connected-fibre assertions are also given in [1 Theorem 2.3 and Lemma 5.5], respectively; the numbering is that of its fourth version.

Lemma 3.2. Every modular flow has an integer lift, and all its integer lifts lie in one component of Ik(G)I_k(G). A possibly-zero Zk\mathbb{Z}_k-flow has an integer lift with absolute values at most k−1k-1 and exactly the same zero edges.

Proof. Represent the modular values by integers r(e)∈{0,…,k−1}r(e) \in\{0,\ldots,k-1\}. The vector r/kr/k has integral divergence. Round it to zz by Lemma 3.1; then F=r−kzF=r-kz is a circulation. If r(e)=0r(e)=0, rounding fixes z(e)=0z(e)=0. Otherwise F(e)F(e) is r(e)r(e) or r(e)−kr(e)-k, both nonzero and of absolute value at most k−1k-1.

For two lifts F,F′F,F' of a nowhere-zero flow, (F′−F)/k(F'-F)/k is an integer circulation valued in {−1,0,1}\{-1,0,1\}. Orient its nonzero edges positively and decompose them into edge-disjoint directed cycles. Adding kk successively on those cycles gives intermediate edge values that are individually old or final, hence are valid integer kk-flow values. □

We will use the integral supply-and-demand form of Hoffman’s circulation theorem; see [3, Section 4.5, Theorems 4.6 and 4.7. Let ℓ,u\ell, u be integer edge bounds with ℓ(e)≤u(e)\ell(e) \le u(e) on every edge, and let bb be an integer vertex vector of total zero. An integer map zz with ℓ≤z≤u\ell\le z \le u and div⁡(z)=b\operatorname{div}(z) = b exists if and only if, for every vertex set UU,

b(U)≤u(δ+(U))−ℓ(δ−(U)).(1)b(U) \le u(\delta^{+}(U)) - \ell(\delta^{-}(U)). \tag*{(1)}

Here δ+(U)\delta^{+}(U) and δ−(U)\delta^{-}(U) are the edges leaving and entering UU. Necessity follows by summing the divergence over UU. For sufficiency put d=b−div⁡(ℓ)d = b - \operatorname{div}(\ell) and give each original edge capacity u−ℓu - \ell. Add a source ss, an arc s→vs \to v of capacity d(v)d(v) for each d(v)>0d(v) > 0, and an arc v→tv \to t of capacity −d(v)-d(v) to a new sink tt for each $d(v) < 0. Write M=∑d(v)>0d(v)M = \sum_{d(v)>0}d(v). The cut with source side {s}∪U\{s\}\cup U has capacity (u−ℓ)(δ+(U))+M−d(U)(u-\ell)(\delta^{+}(U))+M-d(U). Thus all these cuts have capacity at least MM exactly when d(U)≤(u−ℓ)(δ+(U))d(U) \le(u-\ell)(\delta^{+}(U)), which expands to (1). An integral maximum flow of value MM saturates the added arcs; its restriction ww to the original edges has divergence dd, so z=ℓ+wz = \ell+ w is the required map. The complement of UU gives the lower inequality. In particular, the criterion forces the sum of bb on each connected component to be zero. Loops impose no divergence constraint and are chosen independently.

Fix a legal step f→f+cχCf \to f+c\chi_C, where cc is represented by an integer in {1,…,k−1}\{1,\ldots,k-1\}. Choose reference directions along CC, and let r(e)∈{1,…,k−1}r(e) \in\{1,\ldots,k-1\} represent ff. Put

b=div⁡(r)/k,H={e∈E(C):r(e)>k−c},L={e∈E(C):r(e)<k−c}.b = \operatorname{div}(r)/k,\qquad H = \{e \in E(C) : r(e) > k-c\},\qquad L = \{e \in E(C) : r(e) < k-c\}.

No cycle edge has residue k−ck-c. Every integer lift of ff is r−kzr-kz, with zz a 0/10/1 map of divergence bb.

Lemma 3.3. A lift accepting the integer increment cc exists if and only if

b(U)≤∣δ+(U)∣−∣H∩δ−(U)∣for every U.(2)b(U) \le\lvert\delta^{+}(U)\rvert-\lvert H\cap\delta^{-}(U)\rvert\quad\text{for every }U. \tag*{(2)}

A lift accepting c−kc-k exists if and only if

b(U)≤∣δ+(U)∖L∣for every U.(3)b(U) \le\lvert\delta^{+}(U)\setminus L\rvert\quad\text{for every }U. \tag*{(3)}

If neither exists, no direct integer lift of the step exists.

Proof. For increment cc, the lift is forced to be r−kr-k on HH, while either lift works on LL. This pins z=1z=1 on HH. Apply (1) with ℓ=1H\ell=1_H, u=1Eu=1_E. For increment c−kc-k, the lift is forced to be rr on LL and is free on HH; pin z=0z=0 there and take ℓ=0\ell=0, u=1E∖Lu=1_{E\setminus L}.

Any direct integer increment congruent to cc has magnitude at most 2k−22k-2, so besides cc and c−kc-k only c+kc+k and c−2kc-2k are possible. The first is impossible when HH is nonempty; when HH is empty, increment cc is already available. The second is impossible when LL is nonempty; when LL is empty, increment c−kc-k is already available. □

Intervals of a violating cut

Lemma 4.1. If a lift accepting cc does not exist, then c≥3c \ge3 and

∣H∣≥2⌈kc−2⌉.\lvert H\rvert\ge2\left\lceil\frac{k}{c-2}\right\rceil.

If a lift accepting c−kc-k does not exist, then k−c≥3k-c \ge3 and

∣L∣≥2⌈kk−c−2⌉.\lvert L\rvert\ge2\left\lceil\frac{k}{k-c-2}\right\rceil.

Proof. A violating set UU for (2) satisfies b(U)≥∣δ+(U)∣−∣H∩δ−(U)∣+1b(U) \geq|\delta^{+}(U)| - |H \cap\delta^{-}(U)| + 1, because all quantities are integers. Multiply by kk and substitute the divergence of rr. Rearrangement gives

k≤∑e∈H∩δ−(U)(k−r(e))−∑e∈δ+(U)(k−r(e))−∑e∈δ−(U)∖Hr(e).(4)k \leq\sum_{e \in H \cap\delta^{-}(U)} (k-r(e))-\sum_{e \in\delta^{+}(U)} (k-r(e))-\sum_{e \in\delta^{-}(U)\setminus H} r(e). \tag*{(4)}

Every contribution of a crossing edge outside CC is negative. Unless U∩V(C)U \cap V(C) is empty or all of V(C)V(C), it is a union of vertex intervals along CC. Each interval has one entering cycle edge ee and one leaving cycle edge e′e'. Its contribution to the right side is

{r(e′)−r(e),e∈H,r(e′)−r(e)−k,e∈L.\begin{cases} r(e')-r(e), & e \in H,\\ r(e')-r(e)-k, & e \in L. \end{cases}

It is positive only when both boundary edges are in HH and r(e′)>r(e)r(e') > r(e). Such a contribution is at most (k−1)−(k−c+1)=c−2(k-1)-(k-c+1)=c-2. Thus c≤2c \leq2 permits no violation. Otherwise at least ⌈k/(c−2)⌉\lceil k/(c-2)\rceil positive intervals are required. Their boundary edges are pairwise distinct and each interval uses two edges of HH. If UU contains all or none of the cycle vertices, there is no positive contribution, so that case cannot violate (2) either. This also deals with a loop cycle. For the assertion about LL, reverse the cycle and its reference directions, replacing the cycle residues by r′=k−rr'=k-r and the increment by c′=k−cc'=k-c. The new wrap set is H′=LH'=L. A lift accepting k−ck-c on the reversed cycle is precisely a lift accepting c−kc-k on the original cycle, so the first assertion applies.

Corollary 4.2. For every k≥3k \geq3, every legal modular step of increment 11, −1-1, 22 or −2-2 has a direct integer lift.

Proof. For increments 1,21,2, Lemma 4.1 excludes a violating cut for (2). Reverse the cycle for increments −1,−2-1,-2.

Proof of Theorem 2.3. If neither direct lift exists, Lemma 4.1 implies 3≤c≤k−33 \leq c \leq k-3 and

∣E(C)∣≥2⌈kc−2⌉+2⌈kk−c−2⌉.(5)|E(C)| \geq2\left\lceil\frac{k}{c-2}\right\rceil+2\left\lceil\frac{k}{k-c-2}\right\rceil. \tag*{(5)}

Each ceiling is at least two. They cannot both equal two: their denominators would each be at least k/2k/2, but those denominators sum to k−4k-4. Their sum is therefore at least five, giving length at least ten. For k=7k=7, the only remaining increments are 3,43,4; the two terms in (5) are fourteen and eight, giving length at least twenty-two.

The half-modulus step

We treat the half-modulus increment separately before applying the chord induction.

Lemma 5.1. Let k=2dk=2d with d≥2d \geq2. For every legal modular step f→f+dχCf \to f+d\chi_C, all integer lifts of both endpoints lie in one component of Ik(G)I_k(G).

Proof. Reduce ff modulo dd to a possibly-zero flow ww, and let E0E_0 be its zero edges. No edge of CC lies in E0E_0, since its value would be dd and the proposed step would create zero. By Lemma 3.2, choose an integer dd-lift WW of ww with exactly the zero set E0E_0. Reverse reference directions outside E0E_0 so that 1≤W≤d−11 \leq W \leq d-1. This proof uses these new reference directions, including for χC\chi_C; they need not agree with the traversal of CC.

Call a nowhere-zero Z2d\mathbb{Z}_{2d}-flow a state if it reduces to ww modulo dd. Every state agrees with ff on E0E_0, where the only possible nonzero value is dd. For any state hh, the quotient (h−W)/d(h-W)/d is a possibly-zero Z2\mathbb{Z}_2-flow. Its nonzero support is even, so an Eulerian orientation gives an integer circulation JJ with values in {−1,0,1}\{-1,0,1\} and that reduction modulo two. Then F=W+dJF=W+dJ is an integer 2d2d-lift of hh. On E0E_0 it has value dd or −d-d; outside E0E_0 it is nonzero modulo dd and lies within the required bounds.

Let OO be a cycle outside E0E_0 directed positively in the chosen reference directions. Then h−dχOh-d\chi_O is another state, and F−dχOF-d\chi_O is an integer 2d2d-flow: its values on OO lie in [1−2d,d−1][1-2d,d-1] and are nonzero modulo dd. Therefore every such step between states has an adjacent pair of integer lifts.

The integer circulation 2W−χC2W-\chi_C is supported outside E0E_0 and strictly positive there, because 2W≥22W\ge2 and χC∈{−1,0,1}\chi_C\in\{-1,0,1\}. Decompose it, with multiplicity, into directed cycle vectors positive in the reference orientation. Subtract dd on these cycles successively, starting at ff. All states stay nonzero modulo dd outside E0E_0 and unchanged on E0E_0. The total change is −d(2W−χC)≡dχC(mod2d)-d(2W-\chi_C)\equiv d\chi_C\pmod{2d}. Each state step has adjacent integer lifts by the previous paragraph, and connected fibres join these steps into the required path. □

Chords and component correspondence

Proof of Theorem 2.1. For k=2k=2 there is at most one nowhere-zero modular flow, and Lemma 3.2 joins its integer lifts. For k=3k=3, the nonzero residues are 1,−11,-1; for k=4k=4, they are 1,−1,21,-1,2; and for k=5k=5, they are 1,−1,2,−21,-1,2,-2. Corollary 4.2 therefore gives two adjacent integer lifts for every modular step in these cases. For k=6k=6, it handles 1,−1,2,−21,-1,2,-2, while the remaining residue 3=k/23=k/2 is handled by Lemma 5.1. Thus every modular step connects its integer lifting fibres in one component. Lifts exist and fibres are connected by Lemma 3.2; conversely integer paths project to modular walks. This gives the component bijection, including empty flow spaces. □

Lemma 6.1. Let f→f+cχCf\to f+c\chi_C be a legal modular step, and let ee be an edge outside CC joining two distinct nonneighboring vertices of CC. If 2c≠02c\ne0 modulo kk, the step is a sequence of two legal cc-steps on strictly shorter cycles.

Proof. Orient the two cycles C1,C2C_1,C_2 formed by the chord so that χC=χC1+χC2\chi_C=\chi_{C_1}+\chi_{C_2}. In either proposed first step, each old-cycle edge has its initial or final value; the only possible zero is on the chord. Write ss for its value in ff, in either fixed direction along the chord. Its two possible values after the first step are s+cs+c and s−cs-c. They cannot both be zero unless 2c=02c=0. Choose a legal first step; the second reaches the prescribed endpoint. The nonneighbor assumption makes both cycles strictly shorter. □

Proof of Theorem 2.2. For k=2k=2 there is at most one nowhere-zero modular flow, and its integer lifts are connected by Lemma 3.2. Let k≥3k\ge3. We prove by induction on the support-cycle length that every modular step has all its integer lifts in one component. The short cycles are covered by Theorem 2.3 and the connected fibres of Lemma 3.2. A nonzero increment with 2c=02c=0 is possible only for even kk, and then c=k/2c=k/2; Lemma 5.1 applies. Every other long step has the required nonneighbor chord. Lemma 6.1 expresses it as two shorter steps; induction and the connected fibre at the intermediate modular flow join their integer lifts. This proves the induction.

Every modular vertex has integer lifts and every fibre is connected. Every modular edge now connects its two fibres in one integer component. Conversely an integer path projects to a modular walk. These facts give the claimed bijection on components, including empty flow spaces. At k=7k=7 use the short-cycle bound twenty-one instead. □

Statement and definitions

Graphs are finite multigraphs; loops and parallel edges are allowed. A cycle is a connected 2-regular subgraph, including a loop or two parallel edges. Choose a reference direction for every edge. For a cycle CC with a direction of traversal, χC\chi_C is 1 on edges traversed forward, −1-1 on edges traversed backward, and 0 elsewhere. The divergence of an edge map is its outgoing sum minus its incoming sum at each vertex. A loop cancels in this difference. A circulation has divergence zero at every vertex.

For an integer k≥2k \ge2, an integer kk-flow is an integer circulation FF with 1≤∣F(e)∣≤k−11 \le\lvert F(e)\rvert\le k-1 on every edge. The graph F(G,k)\mathcal{F}(G,k) has these flows as vertices; two are adjacent if their difference is aχCa\chi_C for an integer a≠0a \ne0 and a cycle CC with a direction of traversal. Thus both endpoints of a step must be integer kk-flows. All flows use the same reference directions. These flows are the nowhere-zero kk-flows of [1], whose step definition agrees: a circulation supported on one cycle is constant along its traversal. A reconfiguration graph with at most one vertex is regarded as connected; the convention for the empty case agrees with [1].

Write δG(S)\delta_G(S) for the edges with exactly one endpoint in S⊆V(G)S \subseteq V(G), and set

mc⁡(G)=max⁡S⊆V(G)∣δG(S)∣.\operatorname{mc}(G)=\max_{S\subseteq V(G)}\lvert\delta_G(S)\rvert.

Loops belong to no cut. A graph is bridgeless if no edge is a bridge; it need not be connected. A graph is 3-edge-connected if it is connected, has at least two vertices, and every nonempty proper vertex set has a cut of size at least three.

Theorem 7.1. Let GG be a finite bridgeless multigraph. For every integer k≥mc⁡(G)+2k \ge\operatorname{mc}(G)+2, the integer flow reconfiguration graph F(G,k)\mathcal{F}(G,k) is connected.

Esperet et al. [1 Theorem 7.1] prove connectedness at some modulus for each loopless 2-edge-connected graph GG; the modulus chosen in their proof is 36∣E(G)∣(∣V(G)∣+1)36\lvert E(G)\rvert(\lvert V(G)\rvert+1). Theorem 7.1 supplies every modulus at or above the stated threshold, and mc⁡(G)≤∣E(G)∣\operatorname{mc}(G) \le\lvert E(G)\rvert. The threshold still depends on GG; it is not a universal constant.

Positive orientations and one-edge flips

On a loopless graph, the positive orientation DFD_F of a nowhere-zero real circulation FF directs each edge in the direction in which its value is positive. Working with coordinates along an orientation DD is just a change of reference directions, not a change in the definition of adjacency. An orientation is strong if its directed graph is strongly connected.

Lemma 8.1. For a connected loopless graph, an orientation is strong if and only if it has a real circulation positive on every edge. For every integer k≥2k \ge2 and every fixed orientation DD of a loopless graph GG, all integer kk-flows with positive orientation DD lie in one component of F(G,k)\mathcal{F}(G,k).

Proof. In a strong orientation every arc lies on a directed cycle. Summing one such cycle vector for every arc gives a positive integer circulation. Conversely, a positive circulation has arcs in both directions across every nonempty cut, by conservation; on a connected graph this implies strong connectivity.

Let F,HF,H be integer kk-flows positive along DD. Their difference H−FH-F is an integer circulation. Orient its nonzero coordinates positively and decompose it into unit directed cycles, with multiplicity. In the original coordinates these cycle vectors have no cancellation on any edge. Adding them successively to FF leaves each edge value between F(e)F(e) and H(e)H(e), hence in [1,k−1][1,k-1]. Every addition is a legal integer step. ∎

We use Hoffman’s circulation criterion and its integrality assertion [3 Section 4.5, Theorems 4.6 and 4.7, respectively]: for integer bounds ℓ(e)≤u(e)\ell(e) \le u(e) on every arc of a directed graph, there is an integer circulation xx with ℓ≤x≤u\ell\le x \le u if and only if, for every vertex set SS,

ℓ(δ−(S))≤u(δ+(S)).(6)\ell(\delta^{-}(S)) \le u(\delta^{+}(S)). \tag*{(6)}

Here δ−(S)\delta^{-}(S) and δ+(S)\delta^{+}(S) are the entering and leaving arcs, respectively, and a map applied to an edge set means its sum on that set.

Lemma 8.2 (one-edge flip). Let GG be connected and loopless, and let DD, D′D' be strong orientations differing only on one edge aa. If k≥mc⁡(G)+2k \ge\operatorname{mc}(G) + 2, then there are adjacent integer kk-flows whose positive orientations are DD and D′D', respectively.

Proof. Write a=v→ua = v \to u in DD, so a=u→va = u \to v in D′D'. A simple directed path PP from vv to uu in D′D' cannot use aa, whose tail in D′D' is uu: a simple path cannot leave its final vertex and later return to it. Thus PP is also a directed path in D−aD-a. Let CC traverse PP from vv to uu and then aa from uu to $v.

Seek a circulation positive along DD with lower bound 1 on every edge and upper bounds

U(a)=1,U(e)=k−3(e∈E(P)),U(e)=k−1(e∉E(P)∪{a}).\begin{aligned} U(a) &= 1, \\ U(e) &= k - 3 \quad(e \in E(P)), \\ U(e) &= k - 1 \quad(e \notin E(P) \cup\{a\}). \end{aligned}

The existence of two strong orientations differing on aa implies that GG has at least two vertices and a cycle, so mc⁡(G)≥2\operatorname{mc}(G) \ge2 and k≥4k \ge4; these bounds are nonempty.

For a set SS with a nonempty cut, let ii and oo count the arcs of DD entering and leaving SS. Put d=i+o=∣δG(S)∣≤mc⁡(G)d = i + o = |\delta_G(S)| \le\operatorname{mc}(G). Since DD is strong, i,o≥1i,o \ge1. If aa does not leave SS, then

U(δ+(S))−i≥(k−3)o−i=(k−2)o−d≥k−2−d≥0.U(\delta^{+}(S)) - i \ge(k - 3)o - i = (k - 2)o - d \ge k - 2 - d \ge0.

If aa leaves SS, then o≥2o \ge2, because D′D' is also strong. Hence

U(δ+(S))−i≥1+(k−3)(o−1)−i=(k−2)(o−1)+2−d≥k−d≥0.\begin{aligned} U(\delta^{+}(S)) - i &\ge1 + (k - 3)(o - 1) - i \\ &= (k - 2)(o - 1) + 2 - d \ge k - d \ge0. \end{aligned}

Empty cuts satisfy the condition automatically. Thus (6) supplies an integer circulation FF within the displayed bounds.

In coordinates along DD, put F′=F+2χCF' = F + 2\chi_C. The value on aa changes from 1 to −1-1; each value on PP increases by 2 and remains in [3,k−1][3,k - 1]; all others stay unchanged. Thus both maps are integer kk-flows, their difference is one cycle step, and the positive orientation of F′F' is exactly D′D'. □

Connecting the orientations

Lemma 9.1. In a loopless 3-edge-connected graph with at least two vertices, any two strong orientations are joined by a sequence of strong orientations in which consecutive orientations differ on a single edge.

Proof. Fix reference directions and let Z⊆RE(G)Z \subseteq\mathbb{R}^{E(G)} be the vector space of real circulations. For each edge ee put He={z∈Z:z(e)=0}H_e = \{z \in Z : z(e) = 0\}. Because ee lies on a cycle, HeH_e is a proper hyperplane of ZZ. For distinct edges ee, ff, the graph G−fG-f is bridgeless: a bridge there would give a cut of size at most two in GG. Thus G−fG-f has a cycle through ee. Its vector is in HfH_f but not HeH_e, so these hyperplanes are distinct.

The nonempty sign regions of Z∖⋃eHeZ \setminus\bigcup_e H_e correspond exactly to strong orientations, by Lemma 8.1. Each region is an open convex cone in ZZ. Choose a point in each of two prescribed regions. Perturb the first point within its region so that the segment to the second point avoids every intersection He∩HfH_e \cap H_f, e≠fe \ne f. This is possible because each such intersection has codimension two: the first endpoints whose segment meets it lie in a proper linear subspace spanned by that intersection and the second point. A finite union of proper subspaces cannot cover an open region. The segment now crosses the hyperplanes one at a time. At each crossing only one coordinate sign changes, giving the desired sequence of orientations. □

Theorem 7.1 for loopless 3-edge-connected graphs. Take any two integer kk-flows FF, HH. Their positive orientations are strong by Lemma 8.1. Join the orientations by Lemma 9.1. At each one-edge flip, Lemma 8.2 supplies adjacent integer flows with the two prescribed orientations. Lemma 8.1 joins any chosen representatives within an intervening orientation, as well as the first and last representatives to FF, HH. Concatenating these paths joins FF to HH. □

Loops and two-edge cuts

Lemma 10.1. Let GG be connected and bridgeless, and suppose δG(S)={e,f}\delta_G(S) = \{e, f\}. For every k≥2k \ge2, restriction to the remaining edges after contracting ee gives an isomorphism F(G,k)≅F(G/e,k)\mathcal{F}(G,k) \cong\mathcal{F}(G/e,k).

Proof. The edge ee is not a loop. A circulation of G/eG/e extends uniquely to a circulation of GG: choose the value on ee to restore conservation at one original endpoint, after which conservation at the other follows from that at the contracted vertex. Summing conservation over SS shows that the value on ee equals the value on ff, up to the fixed sign of their reference directions. Thus the extension is nonzero and has the required absolute bound on ee. This proves a bijection of integer kk-flows.

A cycle of GG uses either both cut edges or neither, since it crosses any cut an even number of times. If it avoids them, it lies on one side of the cut and remains a cycle after contraction. If it uses them, contracting ee shortens it to a cycle, possibly a loop when the cycle consists of ee, ff. Conversely, in (G/e)−f(G/e)-f the identified vertex is the only possible meeting point of the two original sides. A simple cycle avoiding ff cannot visit that vertex twice, so it stays on one side and lifts to a cycle avoiding ee. A cycle using ff must return through that vertex; splitting the vertex and inserting ee gives a cycle of GG. These correspondences are inverse. They preserve each cycle-step coefficient: in the reverse direction, the cycle vector of the lifted cycle is the unique extension of the cycle vector in G/eG/e. By linearity and uniqueness, the difference of the extended flows has this same coefficient. Hence the flow bijection preserves adjacency in both directions. □

Completion of the proof of Theorem 7.1. First suppose GG is connected. A loop has an independent nonzero integer value in {−(k−1),…,−1,1,…,k−1}\{-(k-1),\ldots,-1,1,\ldots,k-1\}. Any two such values are joined by one loop step, so deleting a loop removes a nonempty complete-graph factor from the Cartesian product description of F(G,k)\mathcal{F}(G,k).

Repeatedly delete loops and contract one edge of a two-edge cut. Both operations preserve connectedness. Deleting a loop changes no cut; every cut after an edge contraction lifts to a cut of the same size before contraction, keeping the two endpoints of the contracted edge on the same side. Thus neither operation creates a bridge or increases mc⁡\operatorname{mc}. Each operation decreases the number of edges, so the process terminates at a connected loopless graph G0G_0 with no cut of size one or two. It has one vertex and no edge, or is 3-edge-connected; also mc⁡(G0)≤mc⁡(G)\operatorname{mc}(G_0) \le\operatorname{mc}(G).

If G0G_0 has no edge, its reconfiguration graph has one vertex. Otherwise the case just proved applies, since k≥mc⁡(G)+2≥mc⁡(G0)+2k \ge\operatorname{mc}(G)+2 \ge\operatorname{mc}(G_0)+2. Transfer connectedness back through Lemma 10.1 and the loop factors.

Finally, for a graph with several connected components, the reconfiguration graph is the Cartesian product of their reconfiguration graphs, since every cycle lies in one component. Each component has maximum cut at most mc⁡(G)\operatorname{mc}(G), so the connected case applies to every factor. An empty factor makes the whole graph empty, which is connected by our convention; otherwise a finite product of connected graphs is connected. □

Remark 10.2. A bridge has value zero in every circulation, by conservation across its cut. Thus a graph with a bridge has no nowhere-zero integer flow, and its reconfiguration graph is empty. The same connectivity conclusion therefore holds trivially for all finite multigraphs under the convention stated above.

Scaling modular components

A nowhere-zero Zk\mathbb{Z}_k-flow is an edge map with nonzero values and divergence zero in Zk\mathbb{Z}_k. Its reconfiguration graph F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) uses the same cycle-step definition, with increments in Zk∖{0}\mathbb{Z}_k \setminus\{0\}. An integer lift of such a flow is an integer kk-flow with the same values modulo kk.

Theorem 11.1. Let GG be any finite multigraph, and let k,m≥2k,m \ge2 be integers. Suppose f,f′f,f' lie in one component of F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k), and F,F′F,F' are integer kk-lifts of f,f′f,f', respectively. Then mFmF and mF′mF' lie in one component of F(G,mk)\mathcal{F}(G,mk).

This statement concerns the scaled original flows. It does not assert connectedness of all integer mkmk-flows, or connectedness of the original lifts at modulus kk. We give the lifting details used in its proof.

Lemma 11.2. If x:E(G)→[0,1]x:E(G)\to[0,1] has integral divergence, there is a map z:E(G)→{0,1}z:E(G)\to\{0,1\} with the same divergence, agreeing with xx on all its integral coordinates.

Proof. If a fractional edge is a loop, it is already a cycle. Otherwise every vertex incident with a fractional edge has at least two fractional edge ends: exactly one would contradict integral divergence. Thus, whenever fractional edges remain, they contain a cycle. Choose a direction on a cycle of fractional edges and add a positive multiple of its cycle vector until some coordinate becomes integral, keeping all coordinates in [0,1][0,1]. No already integral coordinate changes. Repetition proves the claim. □

Lemma 11.3. Every nowhere-zero ZK\mathbb{Z}_K-flow has an integer KK-lift, and all its integer KK-lifts lie in one component of F(G,K)\mathcal{F}(G,K), for every K≥2K\ge2.

Proof. Represent the residues by r(e)∈{1,…,K−1}r(e)\in\{1,\ldots,K-1\}. The map r/Kr/K has integral divergence. Round it to zz by Lemma 11.2; then r−Kzr-Kz is an integer circulation, with every value either r(e)r(e) or r(e)−Kr(e)-K, and is an integer KK-lift.

For two such lifts H,H′H,H', the map (H′−H)/K(H'-H)/K is a circulation with values in {−1,0,1}\{-1,0,1\}. Direct its nonzero edges positively and decompose them into edge-disjoint directed cycles. Adding KK on these cycles successively gives only old or final edge values at each stage, so all intermediate maps are integer KK-flows. □

Lemma 11.4. For K≥3K\ge3, every legal modular step with increment 11 or 22 has a pair of adjacent integer KK-lifts, one at each endpoint.

Proof. Choose reference directions along its cycle CC, and write the initial residues as r(e)∈{1,…,K−1}r(e)\in\{1,\ldots,K-1\}. For increment 11, legality excludes r(e)=K−1r(e)=K-1 on CC. Either representative r(e)r(e) or r(e)−Kr(e)-K therefore remains nonzero and within the integer KK-flow bounds after adding 11. Thus every integer lift accepts this step, and such a lift exists by Lemma 11.3. For increment 2, legality excludes r(e)=K−2r(e) = K - 2 on CC. Apply Lemma 11.2 to x=(r+χC)/Kx = (r + \chi_C)/K, which lies in [0,1]E(G)[0,1]^{E(G)} and has integral divergence. The rounded map zz has the same divergence as r/Kr/K and has z(e)=1z(e) = 1 wherever e∈E(C)e \in E(C) and r(e)=K−1r(e) = K - 1. Thus H=r−KzH = r - Kz is an integer KK-lift with value −1-1 on those edges. Adding 22 changes them to 11. Every other cycle residue is at most K−3K - 3; either of its representatives remains nonzero and within the bounds after adding 22. Consequently H+2χCH + 2\chi_C is the required adjacent integer lift. □

Proof of Theorem 11.1. Multiplication by mm gives an injective homomorphism Zk→Zmk\mathbb{Z}_k \to\mathbb{Z}_{mk}, so mfmf is nowhere zero. The integer flow mFmF is an integer mkmk-lift of it, since m∣F(e)∣≤m(k−1)<mkm|F(e)| \le m(k - 1) < mk; the same holds for mF′mF'.

It suffices to handle one modular step f′=f+cχCf' = f + c\chi_C, represented by an integer 1≤c≤k−11 \le c \le k - 1. In Zmk\mathbb{Z}_{mk} consider

gs=mf+sχC,0≤s≤mc.g_s = mf + s\chi_C,\qquad0 \le s \le mc.

If mm does not divide ss, then on CC every value is congruent to ss or −s-s modulo mm, and is nonzero; outside CC the nonzero values of mfmf are unchanged. The endpoints g0=mfg_0 = mf and gmc=mf′g_{mc} = mf' are also nowhere zero. Take the increasing list consisting of 00, mcmc and all intermediate integers not divisible by mm. Consecutive entries differ by 11 or 22, since m≥2m \ge2. This gives a modular path from mfmf to mf′mf' whose increments are all 11 or 22.

Lemma 11.4, with K=mk≥4K = mk \ge4, supplies adjacent integer lifts at every step. Lemma 11.3 joins the choices within each intermediate fibre, and joins the endpoint choices to mF,mF′mF, mF'. At an intermediate vertex of a longer modular path, the witnesses from the two incident steps lie in the same fibre over its scaled flow; that fibre is connected. Thus the one-step constructions concatenate without choosing integer kk-lifts of the intermediate modular flows. A path of length zero is covered by the same connected-fibre lemma. □

Setting and statements

Let AA be a finite integer matrix with column set EE. It is totally unimodular if each square subdeterminant is 00, 11, or −1-1. An integer kk-flow of AA, for k≥2k \ge2, is a vector F∈ZEF \in\mathbb{Z}^{E} with AF=0AF = 0 and 1≤∣Fe∣≤k−11 \le|F_e| \le k - 1 for every e∈Ee \in E. A modular kk-flow is a vector f∈(Zk)Ef \in(\mathbb{Z}_k)^E with Af=0Af = 0 in Zk\mathbb{Z}_k and fe≠0f_e \ne0 for every ee. A circuit vector is a primitive integer vector in ker⁡A\ker A with nonempty support minimal under inclusion among supports of nonzero real kernel vectors. Primitivity means that its nonzero coordinates have greatest common divisor one. Such a vector is determined up to sign by its support. For a totally unimodular matrix its coordinates belong to {−1,0,1}\{-1,0,1\}, as proved below.

Let Lk(A)\mathcal{L}_k(A) and Mk(A)\mathcal{M}_k(A) have the integer and modular kk-flows, respectively, as vertices. Two vertices are adjacent when their difference is a nonzero scalar multiple of a circuit vector, with the scalar taken over Z\mathbb{Z} or Zk\mathbb{Z}_k, respectively. A step is legal only if both endpoints are vertices. Reduction modulo kk sends an integer step to a modular step or to equality. A graph with at most one vertex is regarded as connected. When EE is empty, the empty vector is the unique flow of either kind.

Theorem 12.1. For every totally unimodular matrix AA and every k∈{2,3,4,5,6}k \in\{2,3,4,5,6\}, reduction modulo kk induces a bijection between the connected components of Lk(A)\mathcal{L}_k(A) and Mk(A)\mathcal{M}_k(A).

Theorem 12.2. For every prime p≥7p \ge7 there is a totally unimodular matrix AA representing the tension space of a finite simple graph for which reduction modulo pp does not induce an injection on connected components. In fact a component of Mp(A)\mathcal{M}_p(A) with two vertices has lifts in at least two different components of Lp(A)\mathcal{L}_p(A).

The integer kernels considered here are regular chain groups in Tutte’s sense [6]: every minimal nonzero support carries a kernel vector whose nonzero coefficients are 1 or −1-1. Oriented incidence matrices give the graphic flow setting; our integer kk-flows are the nowhere-zero kk-flows of Esperet et al. [1]. For these matrices, Theorem 12.1 recovers the graph component correspondence through six, with a shorter proof using rounding directly instead of a cut and interval argument. The implication from modular connectedness to integer connectedness for graph flows is the lifting question of Esperet et al. [1, Problem 2.6]. Theorem 12.1 gives a stronger statement in a broader setting at these small moduli. Theorem 12.2 does not refute that question for graphs: its examples are tension spaces, and their modular reconfiguration graphs are themselves disconnected.

Rounding and conformal circuits

Negating a column of AA and the corresponding flow coordinate preserves total unimodularity and both reconfiguration graphs. We use these coordinate reorientations freely.

Lemma 13.1 (Rounding). Suppose AA is totally unimodular, x∈[0,1]Ex \in[0,1]^E, and AxAx is integral. There is z∈{0,1}Ez \in\{0,1\}^E with Az=AxAz=Ax and ze=xez_e=x_e on every coordinate where xex_e is integral.

Proof. The nonempty bounded polytope defined by these equalities and 0≤z≤10 \le z \le1 has a vertex. Its constraint matrix consists of rows of AA, their negatives, and signed coordinate rows, and is totally unimodular. At a vertex a full-rank square subsystem of active constraints determines the coordinates. Its determinant is 1 or −1-1 and its right-hand side is integral, so that vertex is integral. The assertion is immediate for the empty coordinate set. □

A real vector uu is conformal to YY if supp⁡(u)⊆supp⁡(Y)\operatorname{supp}(u) \subseteq\operatorname{supp}(Y) and ueYe>0u_eY_e > 0 for every e∈supp⁡(u)e \in\operatorname{supp}(u).

Lemma 13.2. Every circuit vector of a totally unimodular matrix has nonzero coordinates in {−1,1}\{-1,1\}. Every integer vector Y∈ker⁡AY \in\ker A is a sum of circuit vectors, all supported on supp⁡(Y)\operatorname{supp}(Y) and conformal to YY.

Proof. The kernel restricted to a circuit support is one-dimensional: two independent vectors on that support could be linearly combined to cancel one coordinate without cancelling them all, contrary to minimality. Thus on a circuit support of size ss, the columns have rank s−1s-1. Choose s−1s-1 independent rows of this restricted matrix. Every remaining row is a linear combination of them, so their kernel is the kernel of the full restricted matrix. The cofactor formula gives a nonzero kernel vector whose coordinates are its signed maximal minors. Minimality of the circuit implies that none of these coordinates vanishes. Total unimodularity therefore makes them all 1 or −1-1. For a singleton circuit the column is zero and the assertion is immediate.

For the decomposition, restrict to supp⁡(Y)\operatorname{supp}(Y) and reorient so that YY is positive there. Choose a nonzero nonnegative real kernel vector with minimal support. Its support is a circuit: otherwise a kernel direction on a proper subset of that support could be added or subtracted until a coordinate vanishes, leaving a nonzero nonnegative vector of smaller support. The corresponding positive circuit vector has value 1 on its support. Subtract it from YY. The result is nonnegative and integral, and its coordinate sum strictly decreases. Repetition terminates at zero. □

Lemma 13.3 (Lifts and fibres). Every modular kk-flow has an integer kk-lift, and all its integer lifts are in one component of Lk(A)L_k(A). More generally a possibly-zero modular kernel vector has an integer lift of absolute values at most k−1k-1 with exactly the same zero coordinates.

Proof. Choose residues re∈{0,…,k−1}r_e \in\{0,\ldots,k-1\}. Then Ar/kAr/k is integral. Round r/kr/k to a binary vector zz by Lemma 13.1 and put F=r−kzF=r-kz. This has AF=0AF=0. A zero residue forces ze=0z_e=0, whereas a nonzero residue gives Fe=reF_e=r_e or re−kr_e-k, both nonzero and within the bound.

For two lifts F,F′F,F' of a nowhere-zero modular vector, (F′−F)/k(F'-F)/k is a kernel vector with coordinates in {−1,0,1}\{-1,0,1\}. Its conformal decomposition from Lemma 13.2 consists of circuit vectors with disjoint supports. Adding kk times these vectors successively changes each coordinate once from its old value to its final value. Every intermediate vector is an integer kk-flow. □

Small steps and half-modulus steps

Lemma 14.1. For k≥3k \ge3, the two endpoints of every legal modular step of increment 11, −1-1, 22, or −2-2 have adjacent integer lifts.

Proof. Reorient so that its circuit vector γ\gamma is 11 on its support CC, and choose residues re∈{1,…,k−1}r_e \in\{1,\ldots,k-1\}. For increment 11, legality excludes re=k−1r_e=k-1 on CC. Both possible integer representatives re,re−kr_e,r_e-k then accept the increment without becoming zero or exceeding the bound. Any integer lift works.

For increment 22, let x=(r+γ)/kx=(r+\gamma)/k. This belongs to [0,1]E[0,1]^E and Ax=Ar/kAx=Ar/k is integral. Round it to binary zz and set F=r−kzF=r-kz. If e∈Ce \in C has re=k−1r_e=k-1, then xe=1x_e=1, so ze=1z_e=1; the step changes Fe=−1F_e=-1 to 11. Legality excludes residue k−2k-2 on CC. On every remaining coordinate of CC, re≤k−3r_e \le k-3, and either integer representative accepts +2+2. Thus F,F+2γF,F+2\gamma are adjacent integer lifts. Reverse the circuit vector for the negative increments. □

Lemma 14.2. Let k=2dk=2d with d≥2d \ge2. For every legal modular step f→f+dγf \to f+d\gamma, all integer lifts of its two endpoints belong to one component of I2d(A)I_{2d}(A).

Proof. Let w=f(modd)w=f\pmod d and let E0E_0 be its zero coordinates. Choose an integer dd-lift WW with exactly that zero set by Lemma 13.3. No coordinate of supp⁡(γ)\operatorname{supp}(\gamma) lies in E0E_0: there the only nonzero value of ff could be dd, and the proposed step would make it zero. Reorient outside E0E_0 so 1≤We≤d−11 \le W_e \le d-1 there.

Call a nowhere-zero modular 2d2d-flow gg a state if it reduces to ww modulo dd. On E0E_0 each state has value dd, so agrees with ff. For an integer representative g~\widetilde{g}, write g~−W=dq\widetilde{g}-W=dq. Then dAq≡0(mod2d)dAq \equiv0 \pmod{2d}, so Aq≡0(mod2)Aq \equiv0 \pmod2; changing the representative changes qq by an even vector. Thus (g−W)/d(g-W)/d is a well-defined modular 2-kernel vector. Lift it to an integer kernel vector J∈{−1,0,1}EJ \in\{-1,0,1\}^E, preserving its zero coordinates. Then F=W+dJF=W+dJ is an integer 2d2d-lift of gg. On E0E_0 it has value dd or −d-d; elsewhere it is nonzero modulo dd and lies in [1−d,2d−1][1-d,2d-1].

Let η\eta be a circuit vector supported outside E0E_0 and positive in this orientation. Then g−dηg-d\eta is another state. The lift FF above accepts −dη-d\eta: its affected values afterward lie in [1−2d,d−1][1-2d,d-1] and remain nonzero modulo dd. Thus every such state step has adjacent integer lifts.

The integer kernel vector Y=2W−γY=2W-\gamma vanishes on E0E_0 and is strictly positive elsewhere, since We≥1W_e \ge1 and γe∈{−1,0,1}\gamma_e \in\{-1,0,1\}. Decompose YY into positive circuit vectors by Lemma 13.2. Starting at ff, subtract dd on these circuits successively. All states stay legal, and the total change is

−dY=−2dW+dγ≡dγ(mod2d).-dY=-2dW+d\gamma\equiv d\gamma\pmod{2d}.

Each state step has adjacent integer lifts; connected fibres concatenate them into a path between the endpoint fibres. □

Proof of Theorem 12.1. At k=2k=2 there is at most one nowhere-zero modular vector, and its fibre is connected. At k=3,4,5k=3,4,5 every nonzero increment is among ±1,±2\pm1,\pm2, so Lemma 14.1 handles every legal modular edge. At k=6k=6 it handles 1,2,4,51,2,4,5, while Lemma 14.2 handles 33. Thus every modular vertex has a lift, every fibre is connected, and every modular edge joins its two fibres in one integer component. Conversely, integer paths reduce to modular walks. These facts give the component bijection, also when the flow spaces are empty. □\square

Tensions as totally unimodular kernels

For a connected loopless graph HH, an integer tension is the vector of oriented differences of an integer vertex potential, taken up to a constant. The modular definition uses vertex potentials in Zk\mathbb{Z}_k. A nowhere-zero modular tension is therefore a proper kk-colouring up to a constant. The integer bound requires all edge differences to have absolute values in {1,…,k−1}\{1,\ldots,k-1\}.

Lemma 15.1. The integer and modular tension spaces of a connected loopless graph with at least two vertices are kernels of one totally unimodular integer matrix. Their circuit steps are exactly shifts by a constant on one side of a bond.

Proof. Let DD be the oriented incidence matrix of HH with one row deleted, and partition its columns into a spanning tree T\mathcal{T} and the remaining edges N\mathcal{N}. The square matrix DTD_{\mathcal{T}} has determinant ±1\pm1, by leaf elimination. Put B=DT−1DNB=D_{\mathcal{T}}^{-1}D_{\mathcal{N}}. An edge vector vv is a tension exactly when vN=BTvTv_{\mathcal{N}}=B^{T}v_{\mathcal{T}}, over both the integers and Zk\mathbb{Z}_k, because DT−1D_{\mathcal{T}}^{-1} is integral. Hence the tension matrix is [−BT I][-B^{T}\ I].

The incidence matrix is totally unimodular: in any square submatrix a column with at most one nonzero permits determinant expansion, while if every column has two nonzeros their signs are opposite and the row sum is zero. For equally sized row and column index sets I,JI,J of BB, replace the tree columns in positions II of DTD_{\mathcal{T}} by the columns of DND_{\mathcal{N}} indexed by JJ, obtaining RR. The matrix DT−1RD_{\mathcal{T}}^{-1}R is an identity matrix with those columns replaced by columns of BB. Expanding along its unchanged identity columns gives det⁡R/det⁡DT=±det⁡B[I,J]\det R/\det D_{\mathcal{T}}=\pm\det B[I,J]. Since RR consists of columns of DD, this determinant is 00 or ±1\pm1. Thus BB is totally unimodular; transposition and adjoining identity columns show the same for [−BT I][-B^{T}\ I].

The minimal nonzero tension supports are bonds. Indeed, a nonconstant real potential has a nonempty level cut contained in its tension support, so minimal support must be a minimal nonempty cut. In a connected graph a nonempty cut is inclusion-minimal exactly when both induced sides are connected; such a cut is a bond. Conversely, when both sides of a cut are connected, any potential with differences supported on that cut is constant on each side. Its primitive tension vector is the signed indicator of the bond. Its scalar multiples shift one side by a constant. □\square

Failure at each prime from seven on

Proof of Theorem 12.2. Fix a prime p≥7p\ge7. Let S={si:i∈Zp}S=\{s_i:i\in\mathbb{Z}_p\} and T={ti:i∈Zp}T=\{t_i:i\in\mathbb{Z}_p\} each induce a complete graph. Insert a cross edge sitjs_i t_j exactly when 1−j+i∉{0,3}1-j+i\notin\{0,3\} modulo pp. This defines a connected simple graph HpH_p with 2p2p vertices and p(p−1)+p(p−2)=2p2−3pp(p-1)+p(p-2)=2p^2-3p edges. By Lemma 15.1 its tension space has a totally unimodular kernel representation AA.

Define colours c(si)=−ic(s_i)=-i and c(tj)=1−jc(t_j)=1-j in Zp\mathbb{Z}_p. The cross-edge differences c(tj)−c(si)c(t_j)-c(s_i) exhaust all residues except 00 and 33. Consequently cc and c′=c+31Sc'=c+31_S are proper colourings, and shifting SS by 33 is a legal bond move.

We first show that their modular tension component has exactly two vertices. In any proper colouring of a KpK_p block, the colours exhaust Zp\mathbb{Z}_p. Suppose a legal move by a≠0a\ne0 modulo pp shifts a subset of that block whose colour set is UU. Avoiding collisions with unchanged vertices requires U+a⊆UU+a\subseteq U, hence U+a=UU+a=U. Primality implies UU is empty or all of Zp\mathbb{Z}_p. Thus each block is shifted wholly or not at all. Modulo a global constant, every nontrivial move shifts SS only. Relative to cc, such a shift is proper only at offsets 0 and 3. These are distinct tensions, so the component is exactly {c,c′}\{c,c'\}.

We show that no integer move joins a lift of cc to a lift of c′c'. Its reduction is a nontrivial modular move, since c≠c′c\ne c'. An integer bond step and its nontrivial reduction have exactly the same support. The block argument therefore makes its side SS or TT. Shifting TT by an integer is, up to a global constant, shifting SS by its negative. Thus the move shifts SS by an integer b≡3(modp)b\equiv3\pmod p. A crossing edge changes its difference by bb; both endpoint differences have absolute value at most p−1p-1, so ∣b∣≤2p−2|b|\le2p-2. Therefore

b∈{3, 3−p, 3+p, 3−2p}.b\in\{3,\,3-p,\,3+p,\,3-2p\}.

For a lift with vertex heights hh, an initial cross difference of residue ρ∈{1,…,p−1}∖{3}\rho\in\{1,\ldots,p-1\}\setminus\{3\} is ρ\rho or ρ−p\rho-p; after the move it decreases by bb.

If b=3b=3, the edges of residues 1 and 2 must use their positive representatives. Thus

h(ti)=h(si)+1,h(ti−1)=h(si)+2.h(t_i)=h(s_i)+1,\qquad h(t_{i-1})=h(s_i)+2.

giving h(ti−1)=h(ti)+1h(t_{i-1})=h(t_i)+1 for every index. Summing around Zp\mathbb{Z}_p is impossible.

If b=3−pb=3-p, edges of residues 4 and 5 must use their negative representatives. Both classes exist because p≥7p\ge7. They give

h(ti−3)=h(si)+4−p,h(ti−4)=h(si)+5−p.h(t_{i-3})=h(s_i)+4-p,\qquad h(t_{i-4})=h(s_i)+5-p.

Again successive tt-heights increase by 1 cyclically, a contradiction.

If b=3+pb=3+p, every initial cross difference would have to be at least 4; a residue-1 edge cannot have that value. If b=3−2pb=3-2p, every initial cross difference would have to be at most 2−p2-p; a residue-(p−1)(p-1) edge, whose possibilities are p−1p-1 and −1-1, cannot have that value. This excludes all four shifts.

Both modular tensions have integer lifts: choose their height representatives in {0,…,p−1}\{0,\ldots,p-1\}. Any integer path between the fibres would reduce to a modular walk inside {c,c′}\{c,c'\} and would contain a first step crossing between these fibres, which has just been excluded. Hence the component map is not injective. □

Remark 16.1 (Scope of the obstruction). The modular tension graph in this example is not connected as a whole. For example, negate all the colours of cc. The differences inside either clique are then negated and are not those of cc or c′c', since pp is odd. This gives a modular tension outside their two-vertex component. Thus the example does not disprove the weaker assertion that modular connectedness implies integer connectedness for tensions. It does show that a universal proof of the stronger component correspondence at 7 cannot apply to every totally unimodular kernel. These examples are not graphic: HpH_p contains K5K_5, so its cycle matroid has an M(K5)M(K_5) minor and is not cographic by [7 Corollary 10.3.5]; equivalently, its bond matroid is not graphic. A proof for graphic flows by the stronger component-correspondence route must exclude these examples. Theorems 12.1 and 12.2 give correspondence through six and failure at every prime from seven on. In particular, six is the largest endpoint of a universal initial interval of moduli; no claim is made about all composite moduli above six.

Liftable steps: the tools from the companion paper

The proof of Theorem 18.1 uses four statements of Section 1 of [4], with their numbers there: the definition of a liftable step [4 Definition 1.7], the lemma on liftable steps [4 Lemma 1.12], the multiplier lemma [4 Lemma 1.11] and the divisor extension [4 Theorem 1.5]. Part (d) of that Lemma 1.12 rests on its Lemma 1.10, and its part (e) rests on its Lemma 1.11 and so on its Theorem 1.5. The proofs are in [4 Section 1], which states its own definitions. Its words agree with those of Section 2: a move there is a step here, and its Mk(G)\mathcal{M}_k(G) and Ik(G)\mathcal{I}_k(G) are the two graphs of flows of this paper; its boundary is the negative of the divergence of Section 2, and the flows are the same. Its Corollary 1.3 is the lifting theorem of Tutte in the form of [1 Theorem 2.3], and its Lemma 1.4 is [1 Lemma 5.5]. Sections 18 to 20 quote the definition and the lemma in their own words.

Six composite moduli: statements and credit

Conventions. All graphs are finite; loops and parallel edges are allowed. Let k≥3k \ge3 be an integer, and fix a reference direction of every edge of a graph GG. A nowhere-zero Zk\mathbb{Z}_k-flow gives every edge a value other than 00 in Zk\mathbb{Z}_k such that at every vertex the sum of the values that leave is equal to the sum of the values that enter. An integer kk-flow gives every edge an integer F(e)F(e) with 1≤∣F(e)∣≤k−11 \le|F(e)| \le k - 1, with the same condition at every vertex. A cycle is a connected subgraph in which every vertex has degree two; a loop is a cycle. A step adds a constant other than 0 along one direction of one cycle (it is subtracted on the edges whose reference direction is against this direction); the result must be a flow of the same kind. The graph F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) has the nowhere-zero Zk\mathbb{Z}_k-flows of GG as its vertices, and the graph F(G,k)\mathcal{F}(G,k) has the integer kk-flows of GG as its vertices; in both, two flows are adjacent if one comes from the other by a step. These are the graphs F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) and F(G,k)\mathcal{F}(G,k) of [1], with a loop counted as a cycle, and the graphs Mk(G)\mathcal{M}_k(G) and Ik(G)\mathcal{I}_k(G) of the other sections of this paper and of [4]. A graph of flows with no vertex or with one vertex counts as connected. The graph GG is Zk\mathbb{Z}_k-flow-connected if F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) is connected, and kk-flow-connected if F(G,k)\mathcal{F}(G,k) is connected. The reduction of an integer kk-flow is the nowhere-zero Zk\mathbb{Z}_k-flow of its values modulo kk, and an integer lift of a nowhere-zero Zk\mathbb{Z}_k-flow ff is an integer kk-flow whose reduction is ff.

The problem and the credit. Reduction modulo kk maps the integer kk-flows onto the nowhere-zero Zk\mathbb{Z}_k-flows, by the lifting theorem of Tutte [1 Theorem 2.3], and the reduction of a step of F(G,k)\mathcal{F}(G,k) is a step of F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) or changes nothing. So, if F(G,k)\mathcal{F}(G,k) is connected, then F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) is connected [1 Observation 2.5]. The lifting question [1 Problem 2.6] asks for a proof of the converse, and [2 Conjecture A] states the equivalence. Part (a) of Theorem 1.1 proves the equivalence, in the form of a bijection of the components, for k≤6k \le6 and every graph, and Section 1 notes that for the graphs with no loop and for 3≤k≤63 \le k \le6 this follows from parts (a) to (d) of the lemma on liftable steps [4 Lemma 1.12]. Part (e) of that lemma is not used there. With part (e) the same deduction works at six more moduli; this is the content of these sections. All tools are from [4]: its Definition 1.7 and its Lemma 1.12, whose part (e) rests on its Lemma 1.11 and its Theorem 1.5. The six moduli were found in the work on that paper and are not stated in it; these sections write the deduction out. The deduction is short, and all its tools are in that paper; Section 17 names them.

Theorem 18.1. Let kk be one of 88, 99, 1212, 1616, 1818, 3636, and let GG be a graph. Then reduction modulo kk induces a bijection between the connected components of F(G,k)\mathcal{F}(G,k) and the connected components of F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k). In particular F(G,k)\mathcal{F}(G,k) is connected if and only if F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) is connected.

Corollary 18.2. Let tt and kk be integers, and let GG be a graph in which every connected component has at most tt vertices of odd degree. Then GG is kk-flow-connected in each of these cases:

(a) t=8t = 8 and kk is 88, 99 or 1212;

(b) t=12t = 12 and kk is 16 or 18;

(c) t=24t = 24 and k=36k = 36.

Theorem 18.1 and Corollary 18.2 say nothing on any other modulus: not that the statement of the theorem holds there, and not that it fails; for k≤6k \le6 the statement of the theorem is part (a) of Theorem 1.1. We give no classification of the moduli for which this proof works. No statement is made on a finite abelian group that is not cyclic.

The liftable residues

Let k≥3k \ge3. An element z≠0z \ne0 of Zk\mathbb{Z}_k is liftable [4 Definition 1.7] if for every graph GG with no loop and every step from a nowhere-zero Zk\mathbb{Z}_k-flow ff to a nowhere-zero Zk\mathbb{Z}_k-flow gg that adds zz along a direction of a cycle, all integer lifts of ff and all integer lifts of gg lie in one connected component of F(G,k)\mathcal{F}(G,k).

Lemma 19.1 ([4 Lemma 1.12]). Let k≥3k \ge3.

(a) Every nowhere-zero Zk\mathbb{Z}_k-flow of a graph GG with no loop has an integer lift, and all its integer lifts lie in one connected component of F(G,k)\mathcal{F}(G,k).

(b) 11 and −1-1 are liftable.

(c) 22 and −2-2 are liftable.

(d) qq and −q-q are liftable for every divisor qq of kk with 1≤q<k1 \le q < k.

(e) Let k=mqk = mq with integers m,q≥2m, q \ge2, and let cc be an integer that is invertible modulo kk, with c≡1c \equiv1 modulo mm and modulo qq. If zz is liftable, then czcz is liftable.

The lemma is quoted in the words of these sections; it is [4 Lemma 1.12], which is proved there. The last sentence of part (e) of [4 Lemma 1.12], a special case for the moduli 4p4p with an odd prime pp, is not repeated here and is not used.

Proposition 19.2. Let kk be one of 8, 9, 12, 16, 18, 36. Then every element z≠0z \ne0 of Zk\mathbb{Z}_k is liftable.

Proof. If zz is liftable by part (b), (c) or (d) of Lemma 19.1, then −z-z is liftable by the same part. In every use of part (e) below, the element zz is liftable by part (b), (c) or (d); so −z-z is liftable also, and with czcz the element c(−z)=−(cz)c(-z) = -(cz) is liftable. So for each kk it is enough to show, for every integer jj with 1≤j≤k/21 \le j \le k/2, that jj or −j-j is liftable modulo kk. In each case we name mm, qq and the numbers cc of part (e); each cc is 1 modulo mm and modulo qq and has no common factor with kk. All congruences are modulo kk.

k=8k = 8, with m=2m = 2, q=4q = 4, c=5c = 5. Part (b) gives 1, part (c) gives 2, part (d) gives 4. Part (e) with z=−1z = -1 gives −5≡3-5 \equiv3.

k=9k = 9, with m=q=3m = q = 3, c=4c = 4. Part (b) gives 1, part (c) gives 2, part (d) gives 3. Part (e) with z=1z = 1 gives 4.

k=12k = 12, with m=2m = 2, q=6q = 6, c=7c = 7. Part (b) gives 1, part (c) gives 2, part (d) gives 3, 4 and 6. Part (e) with z=−1z = -1 gives −7≡5-7 \equiv5.

k=16k = 16, with m=q=4m = q = 4 and c=5c = 5, 9, 13. Part (b) gives 1, part (c) gives 2, part (d) gives 4 and 8. Part (e) gives, with c=5c = 5 and z=1z = 1, the element 5; with c=5c = 5 and z=−2z = -2, the element −10≡6-10 \equiv6; with c=9c = 9 and z=−1z = -1, the element −9≡7-9 \equiv7; with c=13c = 13 and z=−1z = -1, the element −13≡3-13 \equiv3.

k=18k = 18, with m=3m = 3, q=6q = 6 and c=7c = 7, 13. Part (b) gives 1, part (c) gives 2, part (d) gives 3, 6 and 9. Part (e) gives, with c=7c = 7 and z=1z = 1, the element 7; with c=7c = 7 and z=−2z = -2, the element −14≡4-14 \equiv4; with c=13c = 13 and z=−1z = -1, the element −13≡5-13 \equiv5; with c=13c = 13 and z=2z = 2, the element 26≡826 \equiv8. k=36k=36, with m=q=6m=q=6 and c=7,13,19,25,31c=7, 13, 19, 25, 31. Part (b) gives 1, part (c) gives 2, part (d) gives 3, 4, 6, 9, 12 and 18. Part (e) gives, with c=7c=7: for z=1z=1 the element 7, for z=2z=2 the element 14, for z=−3z=-3 the element −21≡15-21 \equiv15, for z=−4z=-4 the element −28≡8-28 \equiv8; with c=13c=13: for z=1z=1 the element 13, for z=−2z=-2 the element −26≡10-26 \equiv10, for z=4z=4 the element 52≡1652 \equiv16; with c=19c=19 and z=−1z=-1 the element −19≡17-19 \equiv17; with c=25c=25 and z=−1z=-1 the element −25≡11-25 \equiv11; with c=31c=31 and z=−1z=-1 the element −31≡5-31 \equiv5.

In each of the six cases every integer from 1 to k/2k/2 is named. □

The proofs of the theorem and of the corollary

Proof of Theorem 18.1. First let GG have no loop. Reduction modulo kk maps an integer kk-flow to a nowhere-zero Zk\mathbb{Z}_k-flow, and it maps a step of F(G,k)\mathcal{F}(G,k) to a step of F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) or to equality. So it maps each connected component of F(G,k)\mathcal{F}(G,k) into one connected component of F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k). By Lemma 19.1(a) every nowhere-zero Zk\mathbb{Z}_k-flow has an integer lift; so every component of F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) contains the reduction of an integer kk-flow. Let FF and F′F' be integer kk-flows whose reductions ff and f′f' lie in one component of F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k), and let f=f0,f1,…,fr=f′f=f_0,f_1,\ldots,f_r=f' be a path of F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k). If r=0r=0, then FF and F′F' are integer lifts of one flow, and they lie in one component of F(G,k)\mathcal{F}(G,k) by Lemma 19.1(a). Let r≥1r\geq1. For every ii the step from fi−1f_{i-1} to fif_i adds an element z≠0z\ne0 of Zk\mathbb{Z}_k along a direction of a cycle, and zz is liftable by Proposition 19.2. So all integer lifts of fi−1f_{i-1} and all integer lifts of fif_i lie in one component of F(G,k)\mathcal{F}(G,k). So all integer lifts of f0,…,frf_0,\ldots,f_r lie in one component, and FF and F′F' are among them. So two components of F(G,k)\mathcal{F}(G,k) with reductions in the same component of F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) are equal. This is the bijection.

Now let GG have loops, and let G∘G^\circ be GG without its loops. A loop adds its value to both sums at its vertex; so the flows of GG of either kind are the flows of G∘G^\circ of that kind together with one allowed value on each loop: one of the 2(k−1)2(k-1) integers jj with 1≤∣j∣≤k−11\leq|j|\leq k-1, or one of the k−1k-1 elements other than 0 of Zk\mathbb{Z}_k. A loop is a cycle, and no other cycle contains a loop. A step on a loop changes the value of this loop only, to any other allowed value; every other step is a step of G∘G^\circ and keeps the values of the loops. So the connected components of F(G,k)\mathcal{F}(G,k) are the sets of all flows of GG whose part on G∘G^\circ lies in one given component of F(G∘,k)\mathcal{F}(G^\circ,k), and the same holds for F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) and F(G∘,Zk)\mathcal{F}(G^\circ,\mathbb{Z}_k). Reduction modulo kk commutes with the passage to the part on G∘G^\circ. So the bijection for G∘G^\circ gives the bijection for GG.

The last sentence of the theorem follows: a graph is connected if and only if it has at most one connected component. □

Proof of Corollary 18.2. (a) By [5], Corollary 86.2 the graph F(G,Zk)\mathcal{F}(G,\mathbb{Z}_k) is connected for every k≥6k\geq6. (b) and (c) By [5], Theorem 82.1, for integers r≥4r\geq4 and k≥3r−2k\geq3r-2, a graph in which every connected component has at most 2r2r vertices of odd degree is Zk\mathbb{Z}_k-flow-connected; use r=6r=6, where 3r−2=163r-2=16, for k=16k=16 and k=18k=18, and r=12r=12, where 3r−2=343r-2=34, for k=36k=36. In each case Theorem 18.1 gives that F(G,k)\mathcal{F}(G,k) is connected. □

Remark 20.1. The modulus 7 is not among the six. The number 7 is a prime; so part (d) of Lemma 19.1 names only q=1q=1 there, and part (e) has no case. So parts (b) to (e) name only ±1\pm1 and ±2\pm2 modulo 7. This says nothing on the truth of the statement of Theorem 18.1 for k=7k=7.

Acknowledgments

This work was done overwhelmingly by AI models and supervised by the author. The models were Anthropic’s Claude and OpenAI’s ChatGPT. The author takes full responsibility for the paper.

References

References

  1. [1]L. Esperet, K. Hendrey, A. Lagoutte, M. Marsello, S. Norin, R. Steiner, Nowhere-zero flow reconfiguration, arXiv:2512.17342v4 (3 July 2026).arxiv.org/abs/2512.17342
  2. [2]D. W. Cranston, J. Li, B. Su, Z. Wang, N. Xu, Reconfiguration of nowhere-zero flows, arXiv:2606.24685v1 (June 23, 2026).arxiv.org/abs/2606.24685
  3. [3]A. Schrijver, A Course in Combinatorial Optimization, lecture notes, 23 March 2017, Section 4.5, Theorems 4.6 and 4.7, https://homepages.cwi.nl/~lex/files/dict.pdf.
  4. [4]D. Goel, Flow reconfiguration with one modulus for all graphs, and Cereceda’s conjecture for bipartite 2-degenerate graphs, version 2.30, October 23, 2026, Part I, https://doi.org/10.5281/zenodo.23603238.
  5. [5]D. Goel, The Cranston–Li–Su–Wang–Xu (2026) conjecture is true, with extensions to graphs with few vertices of odd degree, version 2.30, October 23, 2026, https://doi.org/10.5281/zenodo.23605839.
  6. [6]W. T. Tutte, A class of Abelian groups, Canadian Journal of Mathematics 8 (1956), 13–28, https://doi.org/10.4153/CJM-1956-004-9.
  7. [7]J. Oxley, Matroid Theory, second edition, Oxford University Press, 2011, Corollary 10.3.5.

Paper details

vlnc:W_q22k39fe
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude, ChatGPT

View statement
Looking for related papers…
Contents