WorksMathematics
Integer and modular flow reconfiguration: the moduli up to six, chords, and large moduli
Abstract
For a finite multigraph and an integer , let be the graph on the nowhere-zero -flows of , and the graph on the integer flows of with 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 is connected whenever is connected; its authors write that they do not know how to prove this even for . We prove it for and every graph, in a stronger form: reduction modulo induces a bijection between the components of and of . We prove the same for every 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 is connected for every bridgeless multigraph and every , where is the largest number of edges of a cut of ; and that scaling by carries the components of into components of . With a theorem of Esperet et al. on planar graphs, the first result settles the question for every planar graph and every . The bijection of the components for 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 , for the tensions of a graph on vertices; this does not answer the question for the flows of graphs. For the six moduli 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 this paper does not settle the question on arbitrary graphs.
Introduction
Graphs are finite multigraphs; loops and parallel edges are allowed. Let be an integer. A modular flow is a nowhere-zero -flow of , and an integer -flow is an integer circulation with 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. is the graph on the modular flows and the graph on the integer -flows, with the legal steps as edges. These are the graphs and 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 maps integer -flows onto modular flows, and an integer step to a modular step or to equality. So, if is connected, then 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 be a graph and be an integer. Prove that if is connected, then is also connected.” They write directly after it: “We do not know how to prove the result even in the case .” 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 be a finite multigraph, and let be an integer.
(a) If , then reduction modulo induces a bijection between the connected components of and of .
(b) Suppose that every cycle of 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 . For it holds with nine replaced by twenty-one.
(c) If is bridgeless and , where is the largest number of edges of a cut of , then 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), is connected if and only if is connected; so the implication of the lifting question holds there, for in particular. The statement on the components says more: need not be connected (for six parallel edges and it is not [2 Theorem 2.1]), and then has exactly as many components, and reduction modulo matches them. In case (c) the graph is connected as well, by reduction and lifting (Lemma 3.2); so for these pairs 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 be a planar multigraph, and let be an integer. Then is connected if and only if is connected.
Proof. For this follows from Theorem 1.1 (a). Let ; we show that both graphs are connected. As in § 2, a reconfiguration graph with at most one vertex is regarded as connected. If has a bridge, then has no flow of either kind, and both graphs are empty. Suppose that 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 . So each of and is the Cartesian product of the corresponding graphs of the components of the graph 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.
For 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 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 : 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 , at and at every multiple of 4 with 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 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 -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 , 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 be a finite integer matrix with column set that is totally unimodular: each square subdeterminant is 0, 1 or . An integer -flow of is a vector with and $1 \le |F_e| \le k-1$ for every , and a modular -flow of is a vector with in and for every . A circuit vector is an integer vector in the kernel of 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 (Lemma 13.2). A step adds a nonzero multiple of a circuit vector. and are the graphs on the integer and on the modular -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 and every , reduction modulo induces a bijection between the connected components of and of .
(b) For every prime there is a totally unimodular matrix , representing the tension space of a finite simple graph, for which reduction modulo does not induce an injection on connected components: a component of with two vertices has lifts in at least two different components of .
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 is the oriented incidence matrix of a graph , then the flows of are the flows of and the circuit vectors are the signed indicator vectors of the cycles of ; 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 that consists of two complete graphs on vertices and of edges between them. This graph contains , so its tension space is not the flow space of a graph (see the remark at the end of § 16); and the graph of the example is not connected, so the example does not even contradict the statement “if is connected, then is connected”. What it shows is that a proof of the bijection of the components for the flows of all graphs at a prime 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 .
What was known, and two companion papers
Esperet et al. [1 Theorem 7.1] prove that is connected at some modulus for each loopless 2-edge-connected graph ; the modulus chosen in their proof is . For planar graphs they prove more [1 Corollary 5.9]: for every 2-edge-connected planar graph , every integer and every abelian group with at least seven elements, the graphs and are connected. So the lifting question was answered for these pairs ; 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 and are both connected for every finite bridgeless loopless multigraph if , if , or if is a multiple of 4 with [4 Theorem 9.2]. For one fixed graph it gives every modulus from a bound on: every , where is the number of edges of a longest cycle of , and every if [4 Corollary 10.6]; every if 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 ; and that the implication of the lifting question holds for these graphs for every .
Part (c) of Theorem 1.1 is a bound of the same kind as the bound of [4], with another parameter, and neither contains the other. For the complete graph we have , so (c) gives every , and [4] gives every . For the complete bipartite graph with we have and , so [4] gives every , and (c) gives every . 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
Every legal modular step on a cycle with at most nine edges has two adjacent integer lifts, for every ; for the same holds for at most twenty-one edges (Theorem 2.3).
For every , every legal modular step of size 1, , 2 or has a pair of adjacent integer lifts (Corollary 4.2).
For with and a legal modular step of size , all integer lifts of both endpoints lie in one component of (Lemma 5.1).
Scaling: if two modular flows lie in one component of and , are integer -lifts of them, then and lie in one component of , for every (Theorem 11.1).
If is connected and bridgeless and is a cut of , then and 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 , [4 Lemma 1.12 (a)–(d)] states that all integer lifts of one modular flow lie in one component of , and that for a legal modular step of size , of size , or of size for a divisor of with , all integer lifts of its two endpoints lie in one component. For every nonzero residue is of one of these three kinds. For 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 , as the proof of Lemma 14.1 does here for matrices. Result (iii) is the case 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 , 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 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 (Lemma 3.2). So it is enough to show, for one legal modular step , that some lift of and some lift of lie in one component. A pair of adjacent lifts whose difference lies on 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 in many intervals, and this needs many edges of (Lemma 4.1). So steps of size , always have adjacent lifts, and so has every step on a short cycle. For there is no other size. For 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 splits a step on into two steps of the same size on shorter cycles, unless modulo (Lemma 6.1); the case is the step of size of Lemma 5.1. This gives (b) by induction on the length of the cycle.
Large moduli (Sections 7 to 10). All integer -flows that are positive on the same orientation lie in one component (Lemma 8.1). If two strong orientations differ on one edge and , then Hoffman’s theorem gives two adjacent integer -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 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 with , the maps are nowhere zero modulo for , for , and for every between them that 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 and is integral, then there is with that agrees with wherever 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 (Lemmas 13.3 and 14.1); the step of size for is treated as in the first part (Lemma 14.2). For part (b) of Theorem 1.3, a nowhere-zero tension modulo is a proper colouring with 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 each of the two complete graphs has all colours and is prime, so a step shifts each of them as a whole or not at all. The component of the colouring of the example has two vertices, 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 modulo with ; 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 and . The first part writes and ; the second part writes and 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 and for a matrix , 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 with a direction of traversal, is 1 on edges traversed forward, 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 , a -flow is an edge map with divergence zero in ; a modular flow will mean a nowhere-zero -flow. A circulation has divergence zero at every vertex. An integer -flow is an integer circulation with on every edge. Their reconfiguration graphs are and : a step adds a nonzero constant times , and both endpoints must be flows of the specified kind. An integer lift of a modular flow has the same edge values modulo . Reduction modulo maps an integer step to a modular step or to equality. A reconfiguration graph with at most one vertex is regarded as connected. Our and are the graphs and 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 implies connectivity of . 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 .” 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 is a pair of adjacent integer lifts, one of and one of , whose difference is supported on . We say that a lift accepts an integer increment on if is an integer -flow. A -step means a modular step with increment .
Theorem 2.1. For every finite multigraph and every , reduction modulo induces a bijection between the connected components of and .
Theorem 2.2. Suppose every cycle of 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 , reduction modulo induces a bijection between the connected components of and . For , 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 . For , the same holds for length at most twenty-one.
Our proof for treats increment 3 by a path between the lifting fibres, without requiring a direct integer lift of that step. For , 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 -flow may be lifted with its zero edges kept zero.
Lemma 3.1 (rounding). If has integral divergence, there is with the same divergence and with wherever 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 , as far as possible while staying in . 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 . A possibly-zero -flow has an integer lift with absolute values at most and exactly the same zero edges.
Proof. Represent the modular values by integers . The vector has integral divergence. Round it to by Lemma 3.1; then is a circulation. If , rounding fixes . Otherwise is or , both nonzero and of absolute value at most .
For two lifts of a nowhere-zero flow, is an integer circulation valued in . Orient its nonzero edges positively and decompose them into edge-disjoint directed cycles. Adding successively on those cycles gives intermediate edge values that are individually old or final, hence are valid integer -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 be integer edge bounds with on every edge, and let be an integer vertex vector of total zero. An integer map with and exists if and only if, for every vertex set ,
Here and are the edges leaving and entering . Necessity follows by summing the divergence over . For sufficiency put and give each original edge capacity . Add a source , an arc of capacity for each , and an arc of capacity to a new sink for each $d(v) < 0. Write . The cut with source side has capacity . Thus all these cuts have capacity at least exactly when , which expands to (1). An integral maximum flow of value saturates the added arcs; its restriction to the original edges has divergence , so is the required map. The complement of gives the lower inequality. In particular, the criterion forces the sum of on each connected component to be zero. Loops impose no divergence constraint and are chosen independently.
Fix a legal step , where is represented by an integer in . Choose reference directions along , and let represent . Put
No cycle edge has residue . Every integer lift of is , with a map of divergence .
Lemma 3.3. A lift accepting the integer increment exists if and only if
A lift accepting exists if and only if
If neither exists, no direct integer lift of the step exists.
Proof. For increment , the lift is forced to be on , while either lift works on . This pins on . Apply (1) with , . For increment , the lift is forced to be on and is free on ; pin there and take , .
Any direct integer increment congruent to has magnitude at most , so besides and only and are possible. The first is impossible when is nonempty; when is empty, increment is already available. The second is impossible when is nonempty; when is empty, increment is already available. □
Intervals of a violating cut
Lemma 4.1. If a lift accepting does not exist, then and
If a lift accepting does not exist, then and
Proof. A violating set for (2) satisfies , because all quantities are integers. Multiply by and substitute the divergence of . Rearrangement gives
Every contribution of a crossing edge outside is negative. Unless is empty or all of , it is a union of vertex intervals along . Each interval has one entering cycle edge and one leaving cycle edge . Its contribution to the right side is
It is positive only when both boundary edges are in and . Such a contribution is at most . Thus permits no violation. Otherwise at least positive intervals are required. Their boundary edges are pairwise distinct and each interval uses two edges of . If 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 , reverse the cycle and its reference directions, replacing the cycle residues by and the increment by . The new wrap set is . A lift accepting on the reversed cycle is precisely a lift accepting on the original cycle, so the first assertion applies.
Corollary 4.2. For every , every legal modular step of increment , , or has a direct integer lift.
Proof. For increments , Lemma 4.1 excludes a violating cut for (2). Reverse the cycle for increments .
Proof of Theorem 2.3. If neither direct lift exists, Lemma 4.1 implies and
Each ceiling is at least two. They cannot both equal two: their denominators would each be at least , but those denominators sum to . Their sum is therefore at least five, giving length at least ten. For , the only remaining increments are ; 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 with . For every legal modular step , all integer lifts of both endpoints lie in one component of .
Proof. Reduce modulo to a possibly-zero flow , and let be its zero edges. No edge of lies in , since its value would be and the proposed step would create zero. By Lemma 3.2, choose an integer -lift of with exactly the zero set . Reverse reference directions outside so that . This proof uses these new reference directions, including for ; they need not agree with the traversal of .
Call a nowhere-zero -flow a state if it reduces to modulo . Every state agrees with on , where the only possible nonzero value is . For any state , the quotient is a possibly-zero -flow. Its nonzero support is even, so an Eulerian orientation gives an integer circulation with values in and that reduction modulo two. Then is an integer -lift of . On it has value or ; outside it is nonzero modulo and lies within the required bounds.
Let be a cycle outside directed positively in the chosen reference directions. Then is another state, and is an integer -flow: its values on lie in and are nonzero modulo . Therefore every such step between states has an adjacent pair of integer lifts.
The integer circulation is supported outside and strictly positive there, because and . Decompose it, with multiplicity, into directed cycle vectors positive in the reference orientation. Subtract on these cycles successively, starting at . All states stay nonzero modulo outside and unchanged on . The total change is . 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 there is at most one nowhere-zero modular flow, and Lemma 3.2 joins its integer lifts. For , the nonzero residues are ; for , they are ; and for , they are . Corollary 4.2 therefore gives two adjacent integer lifts for every modular step in these cases. For , it handles , while the remaining residue 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 be a legal modular step, and let be an edge outside joining two distinct nonneighboring vertices of . If modulo , the step is a sequence of two legal -steps on strictly shorter cycles.
Proof. Orient the two cycles formed by the chord so that . In either proposed first step, each old-cycle edge has its initial or final value; the only possible zero is on the chord. Write for its value in , in either fixed direction along the chord. Its two possible values after the first step are and . They cannot both be zero unless . 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 there is at most one nowhere-zero modular flow, and its integer lifts are connected by Lemma 3.2. Let . 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 is possible only for even , and then ; 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 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 with a direction of traversal, is 1 on edges traversed forward, 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 , an integer -flow is an integer circulation with on every edge. The graph has these flows as vertices; two are adjacent if their difference is for an integer and a cycle with a direction of traversal. Thus both endpoints of a step must be integer -flows. All flows use the same reference directions. These flows are the nowhere-zero -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 for the edges with exactly one endpoint in , and set
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 be a finite bridgeless multigraph. For every integer , the integer flow reconfiguration graph is connected.
Esperet et al. [1 Theorem 7.1] prove connectedness at some modulus for each loopless 2-edge-connected graph ; the modulus chosen in their proof is . Theorem 7.1 supplies every modulus at or above the stated threshold, and . The threshold still depends on ; it is not a universal constant.
Positive orientations and one-edge flips
On a loopless graph, the positive orientation of a nowhere-zero real circulation directs each edge in the direction in which its value is positive. Working with coordinates along an orientation 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 and every fixed orientation of a loopless graph , all integer -flows with positive orientation lie in one component of .
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 be integer -flows positive along . Their difference 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 leaves each edge value between and , hence in . 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 on every arc of a directed graph, there is an integer circulation with if and only if, for every vertex set ,
Here and 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 be connected and loopless, and let , be strong orientations differing only on one edge . If , then there are adjacent integer -flows whose positive orientations are and , respectively.
Proof. Write in , so in . A simple directed path from to in cannot use , whose tail in is : a simple path cannot leave its final vertex and later return to it. Thus is also a directed path in . Let traverse from to and then from to $v.
Seek a circulation positive along with lower bound 1 on every edge and upper bounds
The existence of two strong orientations differing on implies that has at least two vertices and a cycle, so and ; these bounds are nonempty.
For a set with a nonempty cut, let and count the arcs of entering and leaving . Put . Since is strong, . If does not leave , then
If leaves , then , because is also strong. Hence
Empty cuts satisfy the condition automatically. Thus (6) supplies an integer circulation within the displayed bounds.
In coordinates along , put . The value on changes from 1 to ; each value on increases by 2 and remains in ; all others stay unchanged. Thus both maps are integer -flows, their difference is one cycle step, and the positive orientation of is exactly . □
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 be the vector space of real circulations. For each edge put . Because lies on a cycle, is a proper hyperplane of . For distinct edges , , the graph is bridgeless: a bridge there would give a cut of size at most two in . Thus has a cycle through . Its vector is in but not , so these hyperplanes are distinct.
The nonempty sign regions of correspond exactly to strong orientations, by Lemma 8.1. Each region is an open convex cone in . 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 , . 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 -flows , . 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 , . Concatenating these paths joins to . □
Loops and two-edge cuts
Lemma 10.1. Let be connected and bridgeless, and suppose . For every , restriction to the remaining edges after contracting gives an isomorphism .
Proof. The edge is not a loop. A circulation of extends uniquely to a circulation of : choose the value on to restore conservation at one original endpoint, after which conservation at the other follows from that at the contracted vertex. Summing conservation over shows that the value on equals the value on , up to the fixed sign of their reference directions. Thus the extension is nonzero and has the required absolute bound on . This proves a bijection of integer -flows.
A cycle of 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 shortens it to a cycle, possibly a loop when the cycle consists of , . Conversely, in the identified vertex is the only possible meeting point of the two original sides. A simple cycle avoiding cannot visit that vertex twice, so it stays on one side and lifts to a cycle avoiding . A cycle using must return through that vertex; splitting the vertex and inserting gives a cycle of . 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 . 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 is connected. A loop has an independent nonzero integer value in . 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 .
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 . Each operation decreases the number of edges, so the process terminates at a connected loopless graph with no cut of size one or two. It has one vertex and no edge, or is 3-edge-connected; also .
If has no edge, its reconfiguration graph has one vertex. Otherwise the case just proved applies, since . 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 , 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 -flow is an edge map with nonzero values and divergence zero in . Its reconfiguration graph uses the same cycle-step definition, with increments in . An integer lift of such a flow is an integer -flow with the same values modulo .
Theorem 11.1. Let be any finite multigraph, and let be integers. Suppose lie in one component of , and are integer -lifts of , respectively. Then and lie in one component of .
This statement concerns the scaled original flows. It does not assert connectedness of all integer -flows, or connectedness of the original lifts at modulus . We give the lifting details used in its proof.
Lemma 11.2. If has integral divergence, there is a map with the same divergence, agreeing with 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 . No already integral coordinate changes. Repetition proves the claim. □
Lemma 11.3. Every nowhere-zero -flow has an integer -lift, and all its integer -lifts lie in one component of , for every .
Proof. Represent the residues by . The map has integral divergence. Round it to by Lemma 11.2; then is an integer circulation, with every value either or , and is an integer -lift.
For two such lifts , the map is a circulation with values in . Direct its nonzero edges positively and decompose them into edge-disjoint directed cycles. Adding on these cycles successively gives only old or final edge values at each stage, so all intermediate maps are integer -flows. □
Lemma 11.4. For , every legal modular step with increment or has a pair of adjacent integer -lifts, one at each endpoint.
Proof. Choose reference directions along its cycle , and write the initial residues as . For increment , legality excludes on . Either representative or therefore remains nonzero and within the integer -flow bounds after adding . Thus every integer lift accepts this step, and such a lift exists by Lemma 11.3. For increment 2, legality excludes on . Apply Lemma 11.2 to , which lies in and has integral divergence. The rounded map has the same divergence as and has wherever and . Thus is an integer -lift with value on those edges. Adding changes them to . Every other cycle residue is at most ; either of its representatives remains nonzero and within the bounds after adding . Consequently is the required adjacent integer lift. □
Proof of Theorem 11.1. Multiplication by gives an injective homomorphism , so is nowhere zero. The integer flow is an integer -lift of it, since ; the same holds for .
It suffices to handle one modular step , represented by an integer . In consider
If does not divide , then on every value is congruent to or modulo , and is nonzero; outside the nonzero values of are unchanged. The endpoints and are also nowhere zero. Take the increasing list consisting of , and all intermediate integers not divisible by . Consecutive entries differ by or , since . This gives a modular path from to whose increments are all or .
Lemma 11.4, with , supplies adjacent integer lifts at every step. Lemma 11.3 joins the choices within each intermediate fibre, and joins the endpoint choices to . 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 -lifts of the intermediate modular flows. A path of length zero is covered by the same connected-fibre lemma. □
Setting and statements
Let be a finite integer matrix with column set . It is totally unimodular if each square subdeterminant is , , or . An integer -flow of , for , is a vector with and for every . A modular -flow is a vector with in and for every . A circuit vector is a primitive integer vector in 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 , as proved below.
Let and have the integer and modular -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 or , respectively. A step is legal only if both endpoints are vertices. Reduction modulo sends an integer step to a modular step or to equality. A graph with at most one vertex is regarded as connected. When is empty, the empty vector is the unique flow of either kind.
Theorem 12.1. For every totally unimodular matrix and every , reduction modulo induces a bijection between the connected components of and .
Theorem 12.2. For every prime there is a totally unimodular matrix representing the tension space of a finite simple graph for which reduction modulo does not induce an injection on connected components. In fact a component of with two vertices has lifts in at least two different components of .
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 . Oriented incidence matrices give the graphic flow setting; our integer -flows are the nowhere-zero -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 and the corresponding flow coordinate preserves total unimodularity and both reconfiguration graphs. We use these coordinate reorientations freely.
Lemma 13.1 (Rounding). Suppose is totally unimodular, , and is integral. There is with and on every coordinate where is integral.
Proof. The nonempty bounded polytope defined by these equalities and has a vertex. Its constraint matrix consists of rows of , 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 and its right-hand side is integral, so that vertex is integral. The assertion is immediate for the empty coordinate set. □
A real vector is conformal to if and for every .
Lemma 13.2. Every circuit vector of a totally unimodular matrix has nonzero coordinates in . Every integer vector is a sum of circuit vectors, all supported on and conformal to .
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 , the columns have rank . Choose 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 . For a singleton circuit the column is zero and the assertion is immediate.
For the decomposition, restrict to and reorient so that 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 . The result is nonnegative and integral, and its coordinate sum strictly decreases. Repetition terminates at zero. □
Lemma 13.3 (Lifts and fibres). Every modular -flow has an integer -lift, and all its integer lifts are in one component of . More generally a possibly-zero modular kernel vector has an integer lift of absolute values at most with exactly the same zero coordinates.
Proof. Choose residues . Then is integral. Round to a binary vector by Lemma 13.1 and put . This has . A zero residue forces , whereas a nonzero residue gives or , both nonzero and within the bound.
For two lifts of a nowhere-zero modular vector, is a kernel vector with coordinates in . Its conformal decomposition from Lemma 13.2 consists of circuit vectors with disjoint supports. Adding times these vectors successively changes each coordinate once from its old value to its final value. Every intermediate vector is an integer -flow. □
Small steps and half-modulus steps
Lemma 14.1. For , the two endpoints of every legal modular step of increment , , , or have adjacent integer lifts.
Proof. Reorient so that its circuit vector is on its support , and choose residues . For increment , legality excludes on . Both possible integer representatives then accept the increment without becoming zero or exceeding the bound. Any integer lift works.
For increment , let . This belongs to and is integral. Round it to binary and set . If has , then , so ; the step changes to . Legality excludes residue on . On every remaining coordinate of , , and either integer representative accepts . Thus are adjacent integer lifts. Reverse the circuit vector for the negative increments. □
Lemma 14.2. Let with . For every legal modular step , all integer lifts of its two endpoints belong to one component of .
Proof. Let and let be its zero coordinates. Choose an integer -lift with exactly that zero set by Lemma 13.3. No coordinate of lies in : there the only nonzero value of could be , and the proposed step would make it zero. Reorient outside so there.
Call a nowhere-zero modular -flow a state if it reduces to modulo . On each state has value , so agrees with . For an integer representative , write . Then , so ; changing the representative changes by an even vector. Thus is a well-defined modular 2-kernel vector. Lift it to an integer kernel vector , preserving its zero coordinates. Then is an integer -lift of . On it has value or ; elsewhere it is nonzero modulo and lies in .
Let be a circuit vector supported outside and positive in this orientation. Then is another state. The lift above accepts : its affected values afterward lie in and remain nonzero modulo . Thus every such state step has adjacent integer lifts.
The integer kernel vector vanishes on and is strictly positive elsewhere, since and . Decompose into positive circuit vectors by Lemma 13.2. Starting at , subtract on these circuits successively. All states stay legal, and the total change is
Each state step has adjacent integer lifts; connected fibres concatenate them into a path between the endpoint fibres. □
Proof of Theorem 12.1. At there is at most one nowhere-zero modular vector, and its fibre is connected. At every nonzero increment is among , so Lemma 14.1 handles every legal modular edge. At it handles , while Lemma 14.2 handles . 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.
Tensions as totally unimodular kernels
For a connected loopless graph , 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 . A nowhere-zero modular tension is therefore a proper -colouring up to a constant. The integer bound requires all edge differences to have absolute values in .
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 be the oriented incidence matrix of with one row deleted, and partition its columns into a spanning tree and the remaining edges . The square matrix has determinant , by leaf elimination. Put . An edge vector is a tension exactly when , over both the integers and , because is integral. Hence the tension matrix is .
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 of , replace the tree columns in positions of by the columns of indexed by , obtaining . The matrix is an identity matrix with those columns replaced by columns of . Expanding along its unchanged identity columns gives . Since consists of columns of , this determinant is or . Thus is totally unimodular; transposition and adjoining identity columns show the same for .
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.
Failure at each prime from seven on
Proof of Theorem 12.2. Fix a prime . Let and each induce a complete graph. Insert a cross edge exactly when modulo . This defines a connected simple graph with vertices and edges. By Lemma 15.1 its tension space has a totally unimodular kernel representation .
Define colours and in . The cross-edge differences exhaust all residues except and . Consequently and are proper colourings, and shifting by is a legal bond move.
We first show that their modular tension component has exactly two vertices. In any proper colouring of a block, the colours exhaust . Suppose a legal move by modulo shifts a subset of that block whose colour set is . Avoiding collisions with unchanged vertices requires , hence . Primality implies is empty or all of . Thus each block is shifted wholly or not at all. Modulo a global constant, every nontrivial move shifts only. Relative to , such a shift is proper only at offsets 0 and 3. These are distinct tensions, so the component is exactly .
We show that no integer move joins a lift of to a lift of . Its reduction is a nontrivial modular move, since . An integer bond step and its nontrivial reduction have exactly the same support. The block argument therefore makes its side or . Shifting by an integer is, up to a global constant, shifting by its negative. Thus the move shifts by an integer . A crossing edge changes its difference by ; both endpoint differences have absolute value at most , so . Therefore
For a lift with vertex heights , an initial cross difference of residue is or ; after the move it decreases by .
If , the edges of residues 1 and 2 must use their positive representatives. Thus
giving for every index. Summing around is impossible.
If , edges of residues 4 and 5 must use their negative representatives. Both classes exist because . They give
Again successive -heights increase by 1 cyclically, a contradiction.
If , every initial cross difference would have to be at least 4; a residue-1 edge cannot have that value. If , every initial cross difference would have to be at most ; a residue- edge, whose possibilities are and , cannot have that value. This excludes all four shifts.
Both modular tensions have integer lifts: choose their height representatives in . Any integer path between the fibres would reduce to a modular walk inside 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 . The differences inside either clique are then negated and are not those of or , since 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: contains , so its cycle matroid has an 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 and 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 be an integer, and fix a reference direction of every edge of a graph . A nowhere-zero -flow gives every edge a value other than in such that at every vertex the sum of the values that leave is equal to the sum of the values that enter. An integer -flow gives every edge an integer with , 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 has the nowhere-zero -flows of as its vertices, and the graph has the integer -flows of as its vertices; in both, two flows are adjacent if one comes from the other by a step. These are the graphs and of [1], with a loop counted as a cycle, and the graphs and 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 is -flow-connected if is connected, and -flow-connected if is connected. The reduction of an integer -flow is the nowhere-zero -flow of its values modulo , and an integer lift of a nowhere-zero -flow is an integer -flow whose reduction is .
The problem and the credit. Reduction modulo maps the integer -flows onto the nowhere-zero -flows, by the lifting theorem of Tutte [1 Theorem 2.3], and the reduction of a step of is a step of or changes nothing. So, if is connected, then 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 and every graph, and Section 1 notes that for the graphs with no loop and for 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 be one of , , , , , , and let be a graph. Then reduction modulo induces a bijection between the connected components of and the connected components of . In particular is connected if and only if is connected.
Corollary 18.2. Let and be integers, and let be a graph in which every connected component has at most vertices of odd degree. Then is -flow-connected in each of these cases:
(a) and is , or ;
(b) and is 16 or 18;
(c) and .
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 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 . An element of is liftable [4 Definition 1.7] if for every graph with no loop and every step from a nowhere-zero -flow to a nowhere-zero -flow that adds along a direction of a cycle, all integer lifts of and all integer lifts of lie in one connected component of .
Lemma 19.1 ([4 Lemma 1.12]). Let .
(a) Every nowhere-zero -flow of a graph with no loop has an integer lift, and all its integer lifts lie in one connected component of .
(b) and are liftable.
(c) and are liftable.
(d) and are liftable for every divisor of with .
(e) Let with integers , and let be an integer that is invertible modulo , with modulo and modulo . If is liftable, then 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 with an odd prime , is not repeated here and is not used.
Proposition 19.2. Let be one of 8, 9, 12, 16, 18, 36. Then every element of is liftable.
Proof. If is liftable by part (b), (c) or (d) of Lemma 19.1, then is liftable by the same part. In every use of part (e) below, the element is liftable by part (b), (c) or (d); so is liftable also, and with the element is liftable. So for each it is enough to show, for every integer with , that or is liftable modulo . In each case we name , and the numbers of part (e); each is 1 modulo and modulo and has no common factor with . All congruences are modulo .
, with , , . Part (b) gives 1, part (c) gives 2, part (d) gives 4. Part (e) with gives .
, with , . Part (b) gives 1, part (c) gives 2, part (d) gives 3. Part (e) with gives 4.
, with , , . Part (b) gives 1, part (c) gives 2, part (d) gives 3, 4 and 6. Part (e) with gives .
, with and , 9, 13. Part (b) gives 1, part (c) gives 2, part (d) gives 4 and 8. Part (e) gives, with and , the element 5; with and , the element ; with and , the element ; with and , the element .
, with , and , 13. Part (b) gives 1, part (c) gives 2, part (d) gives 3, 6 and 9. Part (e) gives, with and , the element 7; with and , the element ; with and , the element ; with and , the element . , with and . Part (b) gives 1, part (c) gives 2, part (d) gives 3, 4, 6, 9, 12 and 18. Part (e) gives, with : for the element 7, for the element 14, for the element , for the element ; with : for the element 13, for the element , for the element ; with and the element ; with and the element ; with and the element .
In each of the six cases every integer from 1 to is named. □
The proofs of the theorem and of the corollary
Proof of Theorem 18.1. First let have no loop. Reduction modulo maps an integer -flow to a nowhere-zero -flow, and it maps a step of to a step of or to equality. So it maps each connected component of into one connected component of . By Lemma 19.1(a) every nowhere-zero -flow has an integer lift; so every component of contains the reduction of an integer -flow. Let and be integer -flows whose reductions and lie in one component of , and let be a path of . If , then and are integer lifts of one flow, and they lie in one component of by Lemma 19.1(a). Let . For every the step from to adds an element of along a direction of a cycle, and is liftable by Proposition 19.2. So all integer lifts of and all integer lifts of lie in one component of . So all integer lifts of lie in one component, and and are among them. So two components of with reductions in the same component of are equal. This is the bijection.
Now let have loops, and let be without its loops. A loop adds its value to both sums at its vertex; so the flows of of either kind are the flows of of that kind together with one allowed value on each loop: one of the integers with , or one of the elements other than 0 of . 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 and keeps the values of the loops. So the connected components of are the sets of all flows of whose part on lies in one given component of , and the same holds for and . Reduction modulo commutes with the passage to the part on . So the bijection for gives the bijection for .
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 is connected for every . (b) and (c) By [5], Theorem 82.1, for integers and , a graph in which every connected component has at most vertices of odd degree is -flow-connected; use , where , for and , and , where , for . In each case Theorem 18.1 gives that 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 there, and part (e) has no case. So parts (b) to (e) name only and modulo 7. This says nothing on the truth of the statement of Theorem 18.1 for .
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]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]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]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]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]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]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]J. Oxley, Matroid Theory, second edition, Oxford University Press, 2011, Corollary 10.3.5.