\section{The scale lemma}\label{b4:sec} From here on $n\ge 109$. The set $S_0$, the good units $K$ and the subgroup $M$ are those of Definition~\ref{b3:def}. A unit of $\Z_n$ is also called a \emph{scale}: a nowhere-zero $\Z_n$-flow $f$ is looked at through the flow $cf$, for a unit $c$. \begin{definition}[Scale set]\label{b4:scaleset} A \emph{scale set} for $n$ is a non-empty subset $M_0$ of $M$ for which there is a number $b_0$ with \begin{condlist}{(ii)} \item[\textup{(i)}] for every $z\ne 0$ in $\Z_n$, at most $b_0$ elements $c$ of $M_0$ have $cz$ in $S_0$; \item[\textup{(ii)}] $|M_0|\ge 9\,b_0$. \end{condlist} Such a number $b_0$ is a \emph{hit bound} of $M_0$. \textup{(}So for every $z\ne 0$ at most one ninth of the elements $c$ of $M_0$ have $cz$ in $S_0$. $M_0$ need not be a subgroup.\textup{)} \end{definition} \begin{remark}\label{b4:Knotempty} If a scale set $M_0$ exists, then $K$ is not empty. Reason: take $c$ in $M_0$ and $z=c^{-1}$. Then $cz=1$ is in $S_0$, so $b_0\ge 1$ and $|M|\ge|M_0|\ge 9$. But $M=\{1\}$ if $K$ is empty. The statements below name the hypothesis ``$K$ is not empty'' at the place where the proof uses it. \end{remark} \begin{lemma}[Scale lemma, general form: a scale that is good for most edges]\label{b4:scale} Let $M_0$ be a scale set, and let $f$ be a nowhere-zero $\Z_n$-flow of a multigraph with $m$ edges. Then there is a scale $c_0$ in $M_0$ such that $c_0f(e)$ is in $S_0$ for at most $m/9$ edges $e$. \end{lemma} \begin{proof} Let $b_0$ be a hit bound of $M_0$. Count the pairs $(c,e)$ of an element $c$ of $M_0$ and an edge $e$ with $cf(e)$ in $S_0$. For every edge $e$ the element $z=f(e)$ is not $0$, so by Definition~\ref{b4:scaleset}~(i) at most $b_0$ elements $c$ form such a pair with $e$. So the number of the pairs is at most $m\,b_0\le m\,|M_0|/9$, by~(ii). Hence some $c_0$ in $M_0$ is in at most $m/9$ pairs. \end{proof} The next lemma is the step that changes the scale. It is used with a shift $x$ that comes from a move, and with $x=0$. \begin{lemma}[One correction]\label{b4:corr} Let $G$ be a multigraph and $H$ a good subgraph of $G$ \textup{(}Definition~\textup{\ref{b1:good})}. Let $c$ be a unit of $\Z_n$ and $\kappa$ a good unit. Let $f$ be a nowhere-zero $\Z_n$-flow of $G$ with $cf(e)\notin S_0$ for every edge $e$ of $H$, and let $x\colon E(H)\to\Z_n$ be any map. Then there is a $\Z_n$-flow $f'$ of $G$ such that \begin{condlist}{(iii)} \item[\textup{(i)}] $f'$ is nowhere zero, and $f'$ is joined to $f$ in $\Fl(G,\Z_n)$; \item[\textup{(ii)}] $f'(e)=f(e)$ for every edge $e$ outside $E(H)$; \item[\textup{(iii)}] $c\kappa\,\bigl(f'(e)+x(e)\bigr)\notin S_0$ for every edge $e$ of $H$. \end{condlist} \end{lemma} \begin{proof} \textup{(1)} \emph{The forbidden integers.} Let $e$ be an edge of $H$. Use Lemma~\ref{b3:G1} with the units $c$ and $c'=c\kappa$ and the element $f(e)+x(e)$; the ratio $c'c^{-1}=\kappa$ is good. So at most one integer $y$ with $|y|\le 27$ has \[ c\kappa\,\bigl(f(e)+x(e)+c^{-1}y\bigr)\in S_0 . \] Let $\psi(e)$ be this integer; if there is none, put $\psi(e)=0$. \textup{(2)} \emph{An integer flow that avoids them.} By Lemma~\ref{b1:bounded}, $H$ has an integer flow $h$ with $|h(e)|\le 27$ and $h(e)\ne\psi(e)$ for every edge $e$ of $H$. \textup{(3)} \emph{Its cycles.} By Lemma~\ref{b1:cycledec}~(b), $h=\chi_{O_1}+\dots+\chi_{O_r}$ with directed cycles $O_j$ of $H$, and every partial sum $h_j=\chi_{O_1}+\dots+\chi_{O_j}$ has $h_j(e)$ between $0$ and $h(e)$. So $|h_j(e)|\le 27$ for every $j$ and every edge $e$ of $H$. Here $h_0=0$ and $h_r=h$. \textup{(4)} \emph{The flows.} Extend every $h_j$ by $0$ outside $E(H)$; this is an integer flow of $G$, and its classes modulo $n$ form a $\Z_n$-flow of $G$. Put $f_j=f+c^{-1}h_j$ for $0\le j\le r$. These are $\Z_n$-flows of $G$, $f_0=f$, and $f_j=f$ outside $E(H)$. \textup{(5)} \emph{They are nowhere zero.} Outside $E(H)$ this holds because $f$ is nowhere zero. Let $e$ be an edge of $H$. Then $cf_j(e)=cf(e)+h_j(e)$. If this is $0$, then $cf(e)=-h_j(e)$ is the class of an integer of absolute value at most $27$, so $cf(e)$ is in $S_0$. This contradicts the hypothesis on $f$. \textup{(6)} \emph{They are joined.} $f_j-f_{j-1}=c^{-1}\chi_{O_j}$, the cycle $O_j$ of $H$ is a cycle of $G$, and $c^{-1}\ne 0$. So $f_{j-1}\to f_j$ is a move of $\Fl(G,\Z_n)$. Put $f'=f_r=f+c^{-1}h$. By (5) and (6), $f'$ has \textup{(i)}; by (4) it has \textup{(ii)}. \textup{(7)} \emph{Property \textup{(iii)}.} Let $e$ be an edge of $H$. Then $c\kappa\,(f'(e)+x(e))=c\kappa\,(f(e)+x(e)+c^{-1}h(e))$. The integer $y=h(e)$ has $|y|\le 27$ and $y\ne\psi(e)$. By the choice of $\psi(e)$ in (1), the element is not in $S_0$. \end{proof} \begin{lemma}[To an $S_0$-free flow]\label{b4:G4} Let $n\ge 109$, let $K$ be not empty, and let $M_0$ be a scale set for $n$. Let $G$ be a bridgeless multigraph \textup{(}loops allowed\textup{)} and $f$ a nowhere-zero $\Z_n$-flow of $G$. Then $f$ is joined in $\Fl(G,\Z_n)$ to an $S_0$-free $\Z_n$-flow of $G$. \end{lemma} \begin{proof} For a bridgeless multigraph $G$ let $P(G)$ be the statement: every nowhere-zero $\Z_n$-flow of $G$ is joined in $\Fl(G,\Z_n)$ to an $S_0$-free $\Z_n$-flow of $G$. A \emph{cut} of a connected multigraph $G$ is the set $\delta(X)$ of the edges with exactly one end in $X$, for a set $X$ of vertices with $\emptyset\ne X\ne V(G)$. A cut is not empty, and a loop is in no cut. $G$ is bridgeless if and only if no cut has exactly one edge. \pfstep{0}{the induction} \textup{(0a)} \emph{Connected graphs are enough.} Let $G_1,\dots,G_r$ be the components of $G$. Each $G_j$ is bridgeless, and the restriction of a nowhere-zero flow of $G$ to $G_j$ is a nowhere-zero flow of $G_j$. A cycle of $G_j$ is a cycle of $G$. So a move of $G_j$, with all values outside $G_j$ fixed, is a move of $G$. Hence $P(G_1),\dots,P(G_r)$, used one after the other, give $P(G)$. \textup{(0b)} \emph{The order.} We prove $P(G)$ for all connected bridgeless multigraphs $G$ by induction on $|V(G)|$; for a fixed number of vertices the loopless graphs come first. So the proof of $P(G)$ can use $P(G')$ for every connected bridgeless multigraph $G'$ with fewer vertices \textup{(}with or without loops\textup{)}. If $G$ has a loop, it can use $P(G')$ also for the loopless connected bridgeless multigraphs $G'$ with $|V(G')|=|V(G)|$. From now on $G$ is connected and bridgeless, and $f$ is a nowhere-zero $\Z_n$-flow of $G$. Exactly one of Step~1, Step~2, Step~3, Steps~4--10 applies to $G$. \pfstep{1}{$G$ has a loop} Let $G_0$ be $G$ without its loops. \textup{(1a)} $G_0$ is connected, loopless and bridgeless, and $V(G_0)=V(G)$. Reason: a loop is in no cut, so $G$ and $G_0$ have the same cuts. \textup{(1b)} The restriction $f_0$ of $f$ to $E(G_0)$ is a nowhere-zero $\Z_n$-flow of $G_0$. Reason: at its vertex a loop adds its value once and subtracts it once. \textup{(1c)} By $P(G_0)$, which (0b) allows, a sequence of moves of $G_0$ leads from $f_0$ to an $S_0$-free flow of $G_0$. Every cycle of $G_0$ is a cycle of $G$. So the same moves, with the values on the loops fixed, lead from $f$ to a nowhere-zero flow $f'$ of $G$ with $f'(e)\notin S_0$ for every edge $e$ that is not a loop. \textup{(1d)} Let $e$ be a loop with $f'(e)$ in $S_0$. Choose $y$ in $\Z_n\setminus S_0$; it exists because $n>55$. The loop $e$ is a cycle of length~$1$, and $y-f'(e)\ne 0$. So the change of the value on $e$ from $f'(e)$ to $y$ is a move, and the new flow is nowhere zero because $y\ne 0$. Do this for every such loop. The last flow is $S_0$-free. \pfstep{2}{$G$ is loopless and has one vertex} Then $G$ has no edge. The only flow of $G$ is the empty map, and it is $S_0$-free. \pfstep{3}{$G$ is loopless and has a cut $\{e_1,e_2\}$ with two edges} Let $\{e_1,e_2\}=\delta(X)$, and let $G'=G/e_1$ be the multigraph obtained by the contraction of $e_1$. So $E(G')=E(G)\setminus\{e_1\}$; the two ends of $e_1$ become one vertex. \textup{(3a)} $G'$ is connected and bridgeless, and $|V(G')|=|V(G)|-1$. Reason: $e_1$ is not a loop; and the cuts of $G'$ are the cuts of $G$ that do not contain $e_1$. \textup{(3b)} There is a sign $\zeta$ in $\{1,-1\}$ such that $g(e_1)=\zeta\,g(e_2)$ for every $\Z_n$-flow $g$ of $G$. Reason: add the conservation equations of the vertices of $X$. Every edge with both ends in $X$ cancels. What is left is $\pm g(e_1)\pm g(e_2)=0$, and the two signs depend only on the reference orientation. \textup{(3c)} Every $\Z_n$-flow $g'$ of $G'$ is the restriction of exactly one $\Z_n$-flow of $G$. Reason: let $v$, $v'$ be the ends of $e_1$. A map on $E(G)$ that is equal to $g'$ on $E(G')$ has conservation at every vertex other than $v$, $v'$. Its two defects at $v$ and at $v'$, counted without $e_1$, have the sum $0$, because $g'$ has conservation at the contracted vertex. So exactly one value on $e_1$ gives conservation at $v$, and then conservation holds at $v'$ too. \textup{(3d)} For a cycle $C'$ of $G'$ with a direction, the edges of $C'$ form in $G$ a cycle, or a path between the two ends of $e_1$; in the second case they form a cycle of $G$ together with $e_1$. So there is a cycle $C$ of $G$ with a direction such that $\chi_C=\chi_{C'}$ on $E(G')$. By (3c), $\chi_C$ is the only flow of $G$ with the restriction $\chi_{C'}$. \textup{(3e)} The restriction of $f$ to $E(G')$ is a nowhere-zero flow of $G'$. By (3a) and (0b), $P(G')$ holds. So there are nowhere-zero flows $f'_0,f'_1,\dots,f'_N$ of $G'$, where $f'_0$ is the restriction of $f$, $f'_N$ is $S_0$-free, and $f'_i-f'_{i-1}=\lambda_i\chi_{C'_i}$ with a cycle $C'_i$ of $G'$ and $\lambda_i\ne 0$. \textup{(3f)} Let $f_i$ be the flow of $G$ with the restriction $f'_i$ \textup{(}by (3c)\textup{)}. Then $f_0=f$. By (3b), $f_i(e_1)=\zeta f_i(e_2)\ne 0$, so $f_i$ is nowhere zero. By (3c) and (3d), $f_i-f_{i-1}=\lambda_i\chi_{C_i}$ for a cycle $C_i$ of $G$: a move. The flow $f_N$ is $S_0$-free: on $E(G')$ it is $f'_N$, and $f_N(e_1)=\zeta f_N(e_2)$ is not in $S_0$ because $S_0=-S_0$. So $f$ is joined to the $S_0$-free flow $f_N$. \pfstep{4}{the remaining case} Now $G$ is connected and loopless, $|V(G)|\ge 2$, and every cut of $G$ has at least three edges. Let $m$ be the number of edges of $G$. \textup{(4a)} Every vertex has degree at least $3$, and $m\ge\tfrac32\,|V(G)|$. Reason: for a vertex $v$, the set $\delta(\{v\})$ is a cut, because $|V(G)|\ge 2$; it has all the edges at $v$, because $G$ is loopless. Add the degrees. \pfstep{5}{a scale for most edges} By Lemma~\ref{b4:scale} there is a scale $c_0$ in $M_0$ such that $c_0f(e)$ is in $S_0$ for at most $m/9$ edges $e$. Put $E'=\{e\in E(G) : c_0f(e)\notin S_0\}$. By (4a), \[ |E'|\ \ge\ \tfrac89\,m\ \ge\ \tfrac89\cdot\tfrac32\,|V(G)|\ =\ \tfrac43\,|V(G)| . \] \pfstep{6}{the good subgraph $H$} There is a good subgraph $H$ of $G$ with $E(H)\subseteq E'$. \textup{(6a)} If $|V(G)|=2$: all edges of $G$ join the two vertices, and $|E'|\ge 8/3$, so $|E'|\ge 3$. Two edges of $E'$ form a cycle $H$ with $2$ edges and $2$ vertices. \textup{(6b)} If $|V(G)|\ge 3$: the multigraph $(V(G),E')$ is loopless and has more than $\tfrac43\,|V(G)|-2$ edges. By Lemma~\ref{b1:extraction} it contains a good subgraph $H$. \textup{(6c)} In both cases $H$ is connected, $|V(H)|\ge 2$, and $c_0f(e)\notin S_0$ for every edge $e$ of $H$. \pfstep{7}{the contracted graph $G^*$ and its path} Let $G^*=G/H$ be the multigraph obtained from $G$ by the identification of $V(H)$ to one vertex $v_H$ and the deletion of $E(H)$. So $E(G^*)=E(G)\setminus E(H)$, and an edge of $E(G^*)$ with both ends in $V(H)$ is a loop of $G^*$. \textup{(7a)} $G^*$ is connected and bridgeless, and $|V(G^*)|\le|V(G)|-1$. Reason: $G$ is connected and $|V(H)|\ge 2$. A cut of $G^*$ is a cut $\delta(X)$ of $G$ with $V(H)\subseteq X$ or $V(H)\cap X=\emptyset$; no edge of $H$ is in such a cut, so the cut has the same edges in $G^*$ and in $G$. \textup{(7b)} The restriction $f^*$ of $f$ to $E(G^*)$ is a nowhere-zero $\Z_n$-flow of $G^*$. Reason: conservation at $v_H$ is the sum of the conservation equations of $f$ at the vertices of $V(H)$; every edge with both ends in $V(H)$ cancels in this sum. \textup{(7c)} By (7a) and (0b), $P(G^*)$ holds. So there are nowhere-zero $\Z_n$-flows $f^*=f^*_0,f^*_1,\dots,f^*_N$ of $G^*$, where $f^*_N$ is $S_0$-free, and $f^*_i-f^*_{i-1}=\lambda_i\chi_{C^*_i}$ with a cycle $C^*_i$ of $G^*$, a direction of it, and $\lambda_i\ne 0$ in $\Z_n$. \textup{(}$N=0$ is possible.\textup{)} \pfstep{8}{cycles of $G$ over the cycles of $G^*$} For every $i$ there is a cycle $C_i$ of $G$ with a direction such that $\chi_{C_i}=\chi_{C^*_i}$ on $E(G^*)$. Reason: if the edges of $C^*_i$ form a cycle of $G$, let $C_i$ be this cycle. Otherwise $C^*_i$ passes through $v_H$, and its edges form in $G$ a path between two different vertices $v$, $v'$ of $V(H)$ whose inner vertices are outside $V(H)$. $H$ is connected, so $H$ has a path from $v'$ to $v$; all its vertices are in $V(H)$. The two paths form a cycle $C_i$ of $G$; give it the direction of $C^*_i$. The edges of $C_i$ that are not in $C^*_i$ are in $E(H)$. \pfstep{9}{the lift of the path} \emph{Claim.} There are nowhere-zero $\Z_n$-flows $f=f_0,f_1,\dots,f_N$ of $G$ and scales $c_0,c_1,\dots,c_N$ in $M$, with the scale $c_0$ of Step~5, such that for every $i$ \begin{condlist}{(I3)} \item[\textup{(I1)}] $f_i=f^*_i$ on $E(G^*)$; \item[\textup{(I2)}] $f_i$ is joined to $f_{i-1}$ in $\Fl(G,\Z_n)$ \textup{(}for $i\ge 1$\textup{)}; \item[\textup{(I3)}] $c_if_i(e)\notin S_0$ for every edge $e$ of $H$. \end{condlist} \textup{(9a)} \emph{The case $i=0$.} $f_0=f$ has (I1) by the definition of $f^*_0=f^*$, and (I3) by (6c). The scale $c_0$ is in $M_0$, and $M_0$ is a subset of $M$. \textup{(9b)} \emph{From $i-1$ to $i$: the new scale.} Let $i\ge 1$, and let $f_{i-1}$ and $c_{i-1}$ be given with (I1) and (I3). Choose $\kappa$ in $K$; here the proof uses that $K$ is not empty. Put $c_i=c_{i-1}\kappa$. It is in $M$, because $M$ is a group that contains $c_{i-1}$ and $\kappa$. \textup{(9c)} \emph{The correction.} Use Lemma~\ref{b4:corr} for the flow $f_{i-1}$, the units $c_{i-1}$ and $\kappa$, and the map $x(e)=\lambda_i\chi_{C_i}(e)$ on $E(H)$; its hypothesis is (I3) for $i-1$. It gives a nowhere-zero flow $f'$ of $G$ that is joined to $f_{i-1}$, with $f'=f_{i-1}$ outside $E(H)$ and \[ c_i\,\bigl(f'(e)+\lambda_i\chi_{C_i}(e)\bigr)\notin S_0\qquad\text{for every edge $e$ of $H$.} \] \textup{(9d)} \emph{The move.} Put $f_i=f'+\lambda_i\chi_{C_i}$. It is a $\Z_n$-flow of $G$. For an edge $e$ of $E(G^*)$, by (9c), (I1) for $i-1$ and Step~8, \[ f_i(e)=f_{i-1}(e)+\lambda_i\chi_{C_i}(e)=f^*_{i-1}(e)+\lambda_i\chi_{C^*_i}(e)=f^*_i(e)\ne 0 . \] This is (I1). For an edge $e$ of $H$, (9c) says $c_if_i(e)\notin S_0$. This is (I3); and $f_i(e)\ne 0$, because $0$ is in $S_0$. So $f_i$ is nowhere zero. Since $\lambda_i\ne 0$, $f'\to f_i$ is a move. With (9c): $f_i$ is joined to $f_{i-1}$. This is (I2). The claim is proved. \pfstep{10}{back to the scale $1$} \textup{(10a)} By (I1), $f_N=f^*_N$ on $E(G^*)$, so $f_N(e)\notin S_0$ for every edge $e$ outside $E(H)$. By (I3), $c_Nf_N(e)\notin S_0$ for every edge $e$ of $H$. \textup{(10b)} The scale $c_N$ is in $M$. By Remark~\ref{b3:sym}, $c_N^{-1}=\kappa_1\kappa_2\cdots\kappa_r$ with $\kappa_1,\dots,\kappa_r$ in $K$ and $r\ge 0$. Put $c_{N,j}=c_N\kappa_1\cdots\kappa_j$ for $0\le j\le r$. So $c_{N,0}=c_N$, $c_{N,r}=1$ and $c_{N,j}=c_{N,j-1}\kappa_j$. \textup{(10c)} Put $g_0=f_N$. For $j=1,\dots,r$ use Lemma~\ref{b4:corr} for the flow $g_{j-1}$, the units $c_{N,j-1}$ and $\kappa_j$, and the map $x=0$. It gives a nowhere-zero flow $g_j$ of $G$ that is joined to $g_{j-1}$, with $g_j=g_{j-1}$ outside $E(H)$ and $c_{N,j}\,g_j(e)\notin S_0$ for every edge $e$ of $H$. The hypothesis of the lemma for $j$ is this property for $j-1$; for $j=1$ it is (10a). \textup{(10d)} Put $g=g_r$. Outside $E(H)$, $g=f_N$, so $g(e)\notin S_0$ by (10a). On $E(H)$, $g(e)=c_{N,r}\,g(e)\notin S_0$. So $g$ is $S_0$-free. By (I2) and (10c), $g$ is joined to $f$. This proves $P(G)$. \end{proof} \begin{remark}[Where the hypotheses are used]\label{b4:where} The scale set is used in Step~5 only, through Lemma~\ref{b4:scale}. ``$M_0$ is a subset of $M$'' is used in (9a), for (10b). ``$K$ is not empty'' is used in (9b). Of the bound on $n$, the proofs of this section use $n>55$ \textup{(}Step~\textup{(1d))} and $n\ge 55$ \textup{(}Lemma~\textup{\ref{b3:G1})}. \end{remark}