\section{Conventions and tools}\label{b1:sec} \subsection{Conventions}\label{b1:conventions} Graphs are finite multigraphs with a fixed reference orientation. Loops are allowed, unless the graph is called loopless; a loop is a cycle of length~$1$. Groups are finite abelian groups. For a cycle $C$ with a direction, $\chi_C$ is its signed indicator. For a group $\Gam$, a \emph{$\Gam$-flow} of $G$ is a map $E(G)\to\Gam$ with conservation at every vertex; it is \emph{nowhere zero} if no value is $0$. An \emph{integer flow} of $G$ is a map $E(G)\to\Z$ with conservation at every vertex. Conservation at a vertex $v$ says: the sum of the values on the edges with head $v$ is equal to the sum of the values on the edges with tail $v$. A loop at $v$ is in both sums. The \emph{support} $\supp(x)$ of a map $x$ on $E(G)$ is the set of the edges $e$ with $x(e)\ne 0$. If the reference orientation of an edge is reversed and the value of every flow on this edge is replaced by its negative, then flows stay flows. No statement of this paper depends on the reference orientation. $\Fl(G,\Gam)$ is the graph on the nowhere-zero $\Gam$-flows of $G$; two flows are adjacent if their difference is $\lambda\chi_C$ for a cycle $C$ of $G$ and $\lambda\ne 0$ \textup{(}a \emph{move}\textup{)}. Two nowhere-zero $\Gam$-flows of $G$ are \emph{joined} if they are in one component of $\Fl(G,\Gam)$, that is, if a sequence of moves leads from one to the other. A multigraph is \emph{bridgeless} if no edge is a bridge; a multigraph with a nowhere-zero $\Gam$-flow is bridgeless. A bridgeless multigraph need not be connected, and it can be without edges; then its only flow is the empty map. An integer also stands for its class in $\Z_n$. $\varphi$ is Euler's function, and $\floor{x}$ is the integer part of $x$. The letter $p$ is always a prime number. \subsection{The statements that are quoted}\label{b1:quoted} The proofs of this paper use one theorem of the literature, Theorem~\ref{b1:seymour}, and statements of the paper~\cite{A} \textup{(}its Part~I\textup{)}, cited by their numbers there. This subsection is the complete list of what is quoted, and the wording is the wording of~\cite{A}, shortened where a part of a statement is not used. Standard facts on finite abelian groups are used without a reference: such a group is a direct product of cyclic groups of prime-power order; it has a subgroup of every order that divides its order; the order of a subgroup divides the order of the group; and the Chinese remainder theorem. \begin{theorem}[Seymour \cite{Seymour}]\label{b1:seymour} Every bridgeless multigraph $G$ has an integer flow $F_6$ with $1\le|F_6(e)|\le 5$ for every edge $e$. \end{theorem} \begin{definition}[Good subgraph \Aref{def:good}]\label{b1:good} A \emph{good subgraph} of a multigraph is a subgraph $H$ of one of two kinds: \begin{condlist}{(SUB)} \item[\textup{(CYC)}] a cycle with at most $5$ edges and at least $2$ vertices; \item[\textup{(SUB)}] a subdivision of a loopless $3$-edge-connected multigraph $H_0$ on at least two vertices, in which every edge of $H_0$ is replaced by a path with at most $3$ edges. \end{condlist} \end{definition} \begin{lemma}[Extraction \Aref{lem:extraction}]\label{b1:extraction} A loopless multigraph $G$ with $|V(G)|\ge 3$ and $|E(G)|>(4/3)\,|V(G)|-2$ contains a good subgraph. \end{lemma} The other statements of~\cite{A} are used in this section only. They are not numbered here. \begin{condlist}{(A5)} \item[\textup{(A1)}] \emph{Integer lifts} \Aref{lem:liftable}, part~(a). Let $k\ge 3$ and let $G$ be a loopless multigraph. Every nowhere-zero $\Z_k$-flow $f$ of $G$ has an integer lift: an integer flow $F$ of $G$ with $F(e)=f(e)$ modulo $k$ and $1\le|F(e)|\le k-1$ for every edge $e$. \item[\textup{(A2)}] \emph{Threads, the auxiliary graph, frames, lists} \Aref{def:threads}, \Aref{def:frame}, \Aref{def:official}, \Aref{def:lists}. Let $H$ be a subdivision as in Definition~\ref{b1:good}~(SUB), and let $A$ be an abelian group. For an edge $t$ of $H_0$, the path $\thr{t}$ of $H$ that replaces $t$ is the \emph{thread} of $t$; it has $\len(t)\in\{1,2,3\}$ edges. Every thread is directed as a path; its edges and the edge $t$ have this direction as reference orientation. There is a graph $Q$, the \emph{auxiliary graph} of $H$. It is a disjoint union of connected graphs $Q_b$. Every edge of $H_0$ is an edge of $Q$ \textup{(}an \emph{original} edge\textup{)}; the other edges of $Q$ are the \emph{expansion} edges. For an $A$-flow $Y$ of $Q$, $\pi(Y)$ is the $A$-flow of $H$ that has the value $Y(t)$ on every edge of $\thr{t}$, for every original edge $t$. Every $H$ has a \emph{frame}. In a frame, every edge of $Q$ is blue or red; the blue edges form a spanning tree $T_b$ of every $Q_b$; the set of the blue edges is the disjoint union of pairs $N_i=\{e_i,f_i\}$, $1\le i\le s$; and every pair $N_i$ has its \emph{official cycle} $C_i$, a directed cycle of $Q$. A \emph{list assignment} $\Lam$ gives every blue edge $t$ of $Q$ a set $\Lam(t)$ of elements of $A$, with $\Lam(t)$ empty for every expansion edge. $\PL{\Lam}$ is the set of the $A$-flows $Y$ of $Q$ with $Y(t)\notin\Lam(t)$ for every blue edge $t$. \item[\textup{(A3)}] \emph{Reverse choice} \Aref{lem:reverse}, part~(a). Let a frame of $H$ and a list assignment $\Lam$ be given. If $|\Lam(e_i)|+|\Lam(f_i)|<|A|$ for every $i$, then for every $A$-flow $Y_0$ of $Q$ there are $x_1,\dots,x_s$ in $A$ with $Y_0+x_1\chi_{C_1}+\dots+x_s\chi_{C_s}$ in $\PL{\Lam}$. \item[\textup{(A4)}] \emph{Corollary~\textup{(i)} of Theorem~M} \Aref{cor:i}. Its words are defined in \Aref{def:stepsystem} and in \Aref{def:conditions}. Let $\Gam$ be a finite abelian group, $B$ a subgroup, $A=\Gam/B$, and $x\mapsto\quo{x}$ the quotient map. A \emph{step system} is a set $\Sig$ of non-zero elements of $\Gam$ with $\Sig=-\Sig$. Put $\SigB=\Sig\cap B$ and $\SigA=\{\quo{\lambda}:\lambda\in\Sig\}\setminus\{0\}$. Two $\Gam$-flows are \emph{$\Sig$-joined} if a sequence of moves $\lambda\chi_C$ with $\lambda$ in $\Sig$ leads from one to the other. For a $\Gam$-flow $f$, $\quo{f}$ is the $A$-flow with the values $\quo{f(e)}$. The four conditions are: \begin{condlist}{(R3$^*$)} \item[\RI] For every set $X$ of at most $6$ elements of $A$, any two elements of $A\setminus X$ are joined by a walk in $A\setminus X$ all of whose steps are in $\SigA$. \item[\RII] For every set $X$ of at most $2$ elements of $B$, any two elements of $B\setminus X$ are joined by a walk in $B\setminus X$ all of whose steps are in $\SigB$. \item[\RIII] Any two non-zero elements of $\Gam$ are joined by a walk in $\Gam\setminus\{0\}$ all of whose steps are in $\Sig$. \item[\AVpp] For every loopless $3$-edge-connected multigraph $G$ with at least two vertices, every nowhere-zero $\Gam$-flow of $G$ is $\Sig$-joined to a nowhere-zero $\Gam$-flow $f'$ such that the multigraph $(V(G),\supp(\quo{f'}))$ contains a good subgraph. \end{condlist} The statement: let $|A|\ge 10$ and $|B|\ge 4$, and let $\Sig$ be a step system with \RI, \RII, \RIII{} and \AVpp. Then any two nowhere-zero $\Gam$-flows of a bridgeless multigraph \textup{(}loops allowed\textup{)} are $\Sig$-joined, and $\Fl(G,\Gam)$ is connected for every finite bridgeless multigraph $G$. \item[\textup{(A5)}] \emph{Lemma~AVG} \Aref{lem:AVG}. Let $\Gam=\Gam_1\times\Gam_2$ with both factors non-trivial, and let $B$ be a subgroup of $\Gam$ with $(|B|-1)/(|\Gam|-1)<1/9$ \textup{(}true for every subgroup of index at least $9$\textup{)}. Let $\Sig$ be a step system that contains a set of generators of $\Gam_1\times 0$ and a set of generators of $0\times\Gam_2$. Then \AVpp{} holds. \textup{(}$B$ need not be a direct factor.\textup{)} \end{condlist} Theorem~\ref{b0:G10} is also a theorem of~\cite{A}, namely \Aref{thm:G10}. It follows from \textup{(A4)} and \textup{(A5)} in a few lines, which are given in Section~\ref{b1:proofG10}. Two remarks, Remark~\ref{b10:rem64} and Remark~\ref{b11:residual}, mention \Aref{thm:bases} and \Aref{thm:Z}; no proof of this paper uses them. \subsection{The group theorem for a subgroup of index at least \texorpdfstring{$10$}{10}}\label{b1:proofG10} \begin{proof}[Proof of Theorem~\textup{\ref{b0:G10}}] The group $\Gam$ is a direct product of cyclic groups of prime-power order. It is not cyclic of prime-power order, and it is not trivial, because $|\Gam|\ge 10\,d\ge 40$. So there are at least two factors, and $\Gam=\Gam_1\times\Gam_2$ with both factors non-trivial. Let $B$ be a subgroup of $\Gam$ of order $d$, and $A=\Gam/B$. Then $|B|=d\ge 4$ and $|A|=|\Gam|/d\ge 10$. Put $\Sig=\Gam\setminus\{0\}$. This is a step system. A move of $\Fl(G,\Gam)$ is a move $\lambda\chi_C$ with $\lambda$ in $\Sig$; so two flows are $\Sig$-joined if and only if they are joined. Here $\SigB=B\setminus\{0\}$, and $\SigA=A\setminus\{0\}$, because every non-zero element of $A$ is the class of a non-zero element of $\Gam$. The hypotheses of \textup{(A4)} hold: \begin{condlist}{(R3$^*$)} \item[\RI] Let $x\ne y$ be elements of $A\setminus X$. Then $y-x$ is in $\SigA$: a walk with one step. \item[\RII] The same in $B\setminus X$, with $\SigB$. \item[\RIII] The same in $\Gam\setminus\{0\}$, with $\Sig$. \item[\AVpp] By \textup{(A5)}. The index of $B$ is $|A|\ge 10$. The set $\Sig$ contains all non-zero elements of $\Gam_1\times 0$ and of $0\times\Gam_2$; they generate these two groups. \end{condlist} So \textup{(A4)} says that $\Fl(G,\Gam)$ is connected for every finite bridgeless multigraph $G$. \end{proof} \subsection{Cycle decomposition and integer lifts}\label{b1:cyclesec} \begin{lemma}[Cycle decomposition]\label{b1:cycledec} Let $G$ be a multigraph. \begin{condlist}{(a)} \item[\textup{(a)}] Every $\Gam$-flow of $G$ is a sum $\lambda_1\chi_{C_1}+\dots+\lambda_r\chi_{C_r}$ with cycles $C_j$ of $G$ and non-zero elements $\lambda_j$ of $\Gam$ \textup{(}$r\ge 0$\textup{)}. \item[\textup{(b)}] Every integer flow $h$ of $G$ is a sum $\chi_{O_1}+\dots+\chi_{O_r}$ with directed cycles $O_j$ of $G$ \textup{(}$r\ge 0$\textup{)} such that every partial sum $h_j=\chi_{O_1}+\dots+\chi_{O_j}$ has $h_j(e)$ between $0$ and $h(e)$ for every edge $e$: $0\le h_j(e)\le h(e)$ or $h(e)\le h_j(e)\le 0$. \end{condlist} \end{lemma} \begin{proof} \textup{(a)} Let $h$ be a $\Gam$-flow of $G$. Let $T_0$ be a spanning forest of $G$: a spanning tree in every component. For an edge $e$ outside $T_0$ let $C_e$ be the cycle that consists of $e$ and of the path of $T_0$ between the two ends of $e$, directed along $e$. \textup{(}If $e$ is a loop, $C_e$ is this loop.\textup{)} The cycle $C_e$ contains no other edge outside $T_0$, and $\chi_{C_e}(e)=1$. So the $\Gam$-flow \[ h'=h-\sum_{e\notin E(T_0)}h(e)\,\chi_{C_e} \] is $0$ on every edge outside $T_0$. Suppose that $h'\ne 0$. The edges with $h'\ne 0$ form a forest with at least one edge. It has a vertex that meets exactly one of these edges. Conservation at this vertex says that $h'$ is $0$ on this edge, a contradiction. So $h'=0$, and $h$ is the sum of the flows $h(e)\chi_{C_e}$ with $h(e)\ne 0$. \textup{(b)} Reverse the reference orientation of every edge $e$ with $h(e)<0$. Then $h\ge 0$, and the claim is: $h$ is a sum of signed indicators of directed cycles that pass all their edges forward. We prove this by induction on $\sum_e h(e)$. If the sum is $0$, take $r=0$. Otherwise some edge has a positive value. If a loop has a positive value, let $O$ be this loop, passed forward. If not, use conservation: at every vertex the sum of $h$ over the edges that enter is equal to the sum over the edges that leave, and the loops can be left out on both sides. So the head of an edge with a positive value is the tail of an edge with a positive value. Start with an edge with a positive value and go on in this way. The walk does not end, so it comes back to a vertex that it has seen. This gives a directed cycle $O$ that passes all its edges forward, with $h>0$ on all its edges. Then $h-\chi_O$ is an integer flow with $h-\chi_O\ge 0$ and with a smaller sum. By induction it is a sum of signed indicators of directed cycles that pass their edges forward. Add $\chi_O$. So $h=\chi_{O_1}+\dots+\chi_{O_r}$, and for every edge $e$ all numbers $\chi_{O_j}(e)$ are $0$ or $1$. Hence $0\le h_j(e)\le h(e)$. In the first reference orientation the values on the reversed edges have the other sign; there $h(e)\le h_j(e)\le 0$. \end{proof} \begin{lemma}[Integer lifts that keep the zeros]\label{b1:lifting} Let $k\ge 2$ and let $f$ be a $\Z_k$-flow of a multigraph $G$ \textup{(}loops allowed; zero values allowed\textup{)}. Then $G$ has an integer flow $F$ with $F(e)=f(e)$ modulo $k$ and $|F(e)|\le k-1$ for every edge $e$, and $F(e)=0$ for every edge $e$ with $f(e)=0$. \end{lemma} \begin{proof} \emph{Let $k\ge 3$.} Let $G'$ be the multigraph with the vertex set $V(G)$ whose edges are the edges $e$ of $G$ that are not loops and have $f(e)\ne 0$. A loop adds nothing to the two sums of the conservation condition, taken together, and an edge with the value $0$ adds nothing. So the restriction $f'$ of $f$ to $E(G')$ is a $\Z_k$-flow of $G'$. It is nowhere zero, and $G'$ is loopless. By \textup{(A1)} there is an integer flow $F'$ of $G'$ with $F'(e)=f'(e)$ modulo $k$ and $1\le|F'(e)|\le k-1$ for every edge $e$ of $G'$. Let $F$ be equal to $F'$ on $E(G')$. Put $F(e)=0$ if $f(e)=0$. For a loop $e$ with $f(e)\ne 0$ let $F(e)$ be the integer in $\{1,\dots,k-1\}$ in the class $f(e)$. For the same reason as before, $F$ is an integer flow of $G$. It has the three properties. \emph{Let $k=2$.} Let $f_4$ be the map $E(G)\to\Z_4$ with $f_4(e)=2$ if $f(e)\ne 0$ and $f_4(e)=0$ if $f(e)=0$. At every vertex, the conservation condition of $f_4$ is twice the conservation condition of $f$, read with the integers $0$ and $1$ in the place of the two classes modulo $2$. So $f_4$ is a $\Z_4$-flow. By the case $k=4$ there is an integer flow $F_4$ of $G$ with $F_4(e)=f_4(e)$ modulo $4$, $|F_4(e)|\le 3$, and $F_4(e)=0$ if $f(e)=0$. All values of $F_4$ are in $\{-2,0,2\}$. So $F=F_4/2$ is an integer flow with values in $\{-1,0,1\}$, with $F(e)=f(e)$ modulo $2$, and with $F(e)=0$ if $f(e)=0$. \end{proof} \subsection{Bounded avoidance}\label{b1:boundedsec} \begin{lemma}[Bounded avoidance]\label{b1:bounded} Let $H$ be a multigraph that is a cycle with at most $5$ edges and at least $2$ vertices, or a subdivision as in Definition~\textup{\ref{b1:good}~(SUB)}, and let $\psi\colon E(H)\to\Z$ be any map. Then $H$ has an integer flow $h$ with $|h(e)|\le 27$ and $h(e)\ne\psi(e)$ for every edge $e$. \end{lemma} \begin{proof} \emph{Let $H$ be a cycle.} Give it a direction. For an integer $x$, the map $x\chi_H$ is an integer flow of $H$, and its value on an edge $e$ is $x$ or $-x$. So for every edge $e$ at most one integer $x$ has $x\chi_H(e)=\psi(e)$. The cycle has at most $5$ edges, and $55$ integers $x$ have $|x|\le 27$. Take one of them that is not excluded by an edge, and put $h=x\chi_H$. \emph{Let $H$ be a subdivision.} We use the notation of \textup{(A2)}. We may assume that the reference orientation of $H$ is that of \textup{(A2)}: if the orientation of an edge $e$ is reversed, replace $\psi(e)$ by $-\psi(e)$. Let $A=\Z_{28}$, and let $A_0=\{0,7,14,21\}$ be its subgroup of order $4$. \textup{(1)} \emph{The forbidden sets.} For an original edge $t$ of $Q$ let $\Phi(t)$ be the set of the classes modulo $28$ of the integers $\psi(e)$, for the edges $e$ of the thread $\thr{t}$. So $|\Phi(t)|\le\len(t)\le 3$. For an expansion edge $t$ let $\Phi(t)$ be empty. \textup{(2)} \emph{The blue edges.} Fix a frame of $H$. For a blue edge $t$ put $\Lam(t)=\Phi(t)+A_0=\{y+x : y\in\Phi(t),\ x\in A_0\}$. This is a list assignment, and $|\Lam(t)|\le 3\cdot 4=12$. So $|\Lam(e_i)|+|\Lam(f_i)|\le 24<28=|A|$ for every $i$. By \textup{(A3)}, with $Y_0=0$, there is an $A$-flow $Y$ of $Q$ with $Y(t)\notin\Phi(t)+A_0$ for every blue edge $t$. \textup{(3)} \emph{The red edges.} Let $\eps$ be a red edge, in the component $Q_b$. It is not an edge of the spanning tree $T_b$. Let $C'_\eps$ be the cycle of $Q_b$ that consists of $\eps$ and of the path of $T_b$ between the two ends of $\eps$, directed along $\eps$. All its other edges are blue. Because $|A_0|=4>|\Phi(\eps)|$, there is $x_\eps$ in $A_0$ with $Y(\eps)+x_\eps\notin\Phi(\eps)$. Put \[ Y'=Y+\sum_{\eps\text{ red}}x_\eps\,\chi_{C'_\eps}. \] This is an $A$-flow of $Q$. On a red edge $\eps$ it has the value $Y(\eps)+x_\eps$, which is not in $\Phi(\eps)$. On a blue edge $t$ it has a value $Y(t)+x$ with $x$ in $A_0$, because $A_0$ is a subgroup. If $Y(t)+x$ is in $\Phi(t)$, then $Y(t)$ is in $\Phi(t)-x$, a subset of $\Phi(t)+A_0$; this is false by \textup{(2)}. So $Y'(t)\notin\Phi(t)$ for every edge $t$ of $Q$. \textup{(4)} \emph{The flow of $H$.} The map $\pi(Y')$ is a $\Z_{28}$-flow of $H$. Let $e$ be an edge of $H$, on the thread $\thr{t}$. Then $\pi(Y')(e)=Y'(t)$ is not in $\Phi(t)$, and the class of $\psi(e)$ is in $\Phi(t)$. So $\pi(Y')(e)$ is not the class of $\psi(e)$. \textup{(5)} \emph{The integer flow.} By Lemma~\ref{b1:lifting} with $k=28$, $H$ has an integer flow $h$ with $h(e)=\pi(Y')(e)$ modulo $28$ and $|h(e)|\le 27$ for every edge $e$. If $h(e)=\psi(e)$ for some edge $e$, then $\pi(Y')(e)$ is the class of $\psi(e)$. By \textup{(4)} this is false. \end{proof}