# Characterising Improvements in Photometric Redshift Probability Density
Functions with Galaxy Morphology

John Y. H. Soo<EMAIL_ADDRESS>School of Physics, Universiti Sains Malaysia,
11800 USM, Pulau Pinang, Malaysia.  Benjamin Joachimi<EMAIL_ADDRESS>Department of Physics and Astronomy, University College London, Gower Street,
London WC1E 6BT, UK.

###### Abstract

In this work, we studied the impact of galaxy morphology on photometric
redshift (photo-$z$) probability density functions (PDFs). By including galaxy
morphological parameters like the radius, axis-ratio, surface brightness and
the Sérsic index in addition to the $ugriz$ broadbands as input parameters, we
used the machine learning photo-$z$ algorithm annz$2$ to train and test on
galaxies from the Canada-France-Hawaii Telescope Stripe-82 (CS82) Survey.
Metrics like the continuous ranked probability score (CRPS), probability
integral transform (PIT), Bayesian odds parameter, and even the width and
height of the PDFs were evaluated, and the results were compared when
different number of input parameters were used during the training process. We
find improvements in the CRPS and width of the PDFs when galaxy morphology has
been added to the training, and the improvement is larger especially when the
number of broadband magnitudes are lacking.

##  I Introduction

In the recent development of photometric redshifts (photo-$z$’s), the use of
probability distribution functions (PDFs, or $p(z)$) has become much sought
after. Since the $p(z)$ of a galaxy produced may provide more information than
a point estimate photo-$z$, many have dedicated their time into developing and
improving the ways $p(z)$’s are generated [1, 2]. Other than being able to
show the probability of multiple peaks, the $p(z)$’s produced for every galaxy
in a sample could be stacked together to form a smooth photo-$z$ distribution
$n(z)$. Many have found that this form of $n(z)$ has showed better results in
weak lensing analyses [3, 4].

The quality of the $p(z)$’s produced by a photo-$z$ algorithm, however, is
difficult to assess: unlike spectroscopic redshifts, there is no ’true’ $p(z)$
for a certain galaxy to be compared with. Many recent and ongoing works have
been dedicated to introduce and assess quality metrics for $p(z)$’s [5, 6].
Examples of such quality metrics include the continuous ranked probability
score (CRPS), probability integral transform (PIT), and the quantile-quantile
(QQ) plot, in which the latter is a graphical representation of the PIT [2].

In this work, we are interested to characterise some of these $p(z)$ metrics
by studying if an improvement in the photo-$z$ point estimates would be
reflected in an improvement in the $p(z)$ metrics. In particular, we study
quantitatively if the improvement in photo-$z$ brought by including galaxy
morphological parameters in the training of an artificial neural network (ANN)
would reflect an improvement in the $p(z)$ metrics. This is important in its
own right, as it helps producers of photo-$z$’s to calibrate their algorithms
to produce ’better’ $p(z)$’s, so to say.

This work is a quick follow-up study to the work of Soo et al. (2018), in
which they showed that galaxy morphology improves the point estimate
photo-$z$’s of galaxies in the CS82 sample, and the magnitude of improvement
increases with decreasing number of broadband filters used [7]. Using this as
the basis of our definition of ’improvement’, we extend Soo’s qualitative
analysis on PDFs into a quantitative one.

##  II Methodology and Data Sample Used

In this work, we use the exact same data sample, photo-$z$ algorithm and input
parameters used in [7]. These would be briefly introduced below, but the
reader could refer to [7] for more details.

The galaxy sample used is constructed by cross-matching data from various
surveys: it uses $ugriz$ broadband photometry from the Sloan Digital Sky
Survey (SDSS) Stripe-$82$ Coadd [8], high-quality morphology from the Canada-
France-Hawaii Telescope Stripe-$82$ (CS82) Survey [9], and spectroscopic
redshifts from SDSS, DEEP2, WiggleZ and the VIMOS VLT Deep Survey (VVDS) [10,
11, 12, 13]. This sample contains $59498$ galaxies, which is divided equally
into $3$ sets for training, validation and testing respectively.

The photo-$z$ algorithm used is annz$2$ [14], it is a powerful package capable
of utilising several machine learning methods to estimate photo-$z$ point
estimates and PDFs of galaxies. Using the same settings as those in [7],
several runs of photo-$z$’s for the same set of galaxies are produced, in each
run we vary the number of broadband magnitudes used as training inputs (e.g.
$i$, $ri$, $gri$, $ugri$, $ugriz$ and etc), in the same fashion shown in
Section $6.1$ of [7]. These runs are repeated by adding $5$ morphological
parameters as training inputs, these parameters are the galaxy radius ($r$),
axial ratio ($q$), mean surface brightness ($\mu$), Sérsic index ($n$) and
shape probability ($p$). These latter runs are known as the ’with morphology’
runs, which quality metrics will be compared to the former ’without
morphology’ runs. In [7] it has been established that the photo-$z$ point
estimate metrics (root-mean square error, $68$th percentile error and outlier
rate) are generally better in the ’with morphology’ runs.

We note that the results shown in [7] have been reweighted with respect to the
CS82 target sample so to reflect its performance on that sample. In this work,
however, we consider both the weighted and unweighted cases to see if there
are differences in results between the two.

##  III Results and Discussion

###  III.1 Metrics Used

To evaluate quantitatively the overall impact of galaxy morphology on the
$p(z)$’s produced, we assess the mean value of several metrics and
characteristics of each individual galaxy $p(z)$. A total of $5$ metrics will
be assessed:

  1. 1.

The mean CRPS value ($\rho_{\textrm{CRPS}}$), it tells us how close the
position of the true redshift is located to the peak of the $p(z)$, the
smaller the value the better the fit [2];

  2. 2.

The mean PIT value ($\rho_{\textrm{PIT}}$), it tells us if the $p(z)$ produced
have adequately defined widths, a large value indicates that the $p(z)$’s are
either too wide or too narrow [2];

  3. 3.

The mean Bayesian odds ($\bar{\Theta}$), a value between $0$ and $1$, it
measures the confidence of the PDF produced, the closer to $1$ the more
confident and reliable the $p(z)$ [7];

  4. 4.

The mean PDF height ($\bar{h}$), which we assume that the higher the better;
and

  5. 5.

The mean PDF $68$th percentile width ($\bar{w}_{68}$), which we assume the
narrower the better.

We note that these values or metrics are not expected to correlate with one
another, e.g. a high $\rho_{\textrm{CRPS}}$ (accurately peaked) does not imply
a low $\rho_{\textrm{PIT}}$ (correctly shaped).

###  III.2 Impact of Galaxy Morphology on $p(z)$

Figure 1: Comparison of the mean CRPS ($\rho_{\textrm{CRPS}}$, first row) and
root-mean-square PIT value ($\rho_{\textrm{PIT}}$, second row) when morphology
is added to the training (green circles) on the unweighted (left) and weighted
(right) CS82 training sample. Also shown are the mean odds ($\bar{\Theta}$,
third row), mean peak height ($\bar{h}$, fourth row) and mean $68\%$ width
($\bar{w}_{68}$ last row) of the $p(z)$ produced for each case. The grey lines
indicate the metric value of the pure $ugriz$ run.

The values of $\rho_{\textrm{CRPS}}$, $\rho_{\textrm{PIT}}$, $\bar{\Theta}$,
$\bar{h}$ and $\bar{w}_{68}$ are calculated for both the unweighted and
weighted CS82 samples, for cases when trained with different numbers of
magnitudes, with and without morphology, and the results are shown in Fig. 1.
Overall, we see that for both cases most metrics experience more improvement
than degradation when morphology is added to training, and the trend of
smaller improvement in with increasing number of bands used is also seen in
most metrics. Notably $\rho_{\textrm{CRPS}}$, we see that galaxy morphology
improves the forecast of the $p(z)$ immensely in both the weighted and
unweighted samples, in most cases improvements of at least $5\%$ are achieved.

The change in $\rho_{\textrm{PIT}}$ is somewhat different from that of
$\rho_{\textrm{CRPS}}$: while we see improvement in the unweighted sample,
degradation in seen when the training sample is weighted. The reason for an
increase in $\rho_{\textrm{PIT}}$ is not easy to pin down just by merely
looking at the metric alone, since it could go both ways: either the widths of
the $p(z)$ are going too narrow, or too wide. But with the values of
$\bar{w}_{68}$ generally decreasing, we deduce that the sizes of the $p(z)$
have turned narrower than they should be with the inclusion of morphology.

In regards to $\bar{\Theta}$, for a $5$ $ugriz$ band training with morphology
we find that the change in $\bar{\Theta}$ is almost negligible with morphology
in the unweighted case: $\bar{\Theta}$ increased from $0.950$ to $0.951$ when
multiple morphological parameters are included, partly because $\bar{\Theta}$
is very high to begin with. However we see a general improvement in both the
unweighted and weighted case when morphology is added to the training, which
indicates that morphology is indeed helping the ANN to improve the confidence
in photo-$z$ values. We also see a direct correlation between the improvement
of $\bar{\Theta}$ and $\rho_{\textrm{CRPS}}$, this is expected since both
measure how well the expected redshift has been encapsulated within the PDF.
However when checked for individual galaxies, we have verified that there is
almost no correlation between the improvement in the point estimate photo-$z$
and the improvement in $\Theta$ for individual galaxies when morphology is
added. This suggests that a galaxy with high $\Theta$ does not necessarily
dictate a better photo-$z$ point estimate, although it remains sufficiently
useful to remove outliers across an entire sample of galaxies [7].

The change in $\bar{w}_{68}$ follows a similar trend as $\bar{\Theta}$, where
we see that morphology on average has successfully reduced the widths of the
$p(z)$. However, the impact of morphology on $\bar{h}$ shows a different
story: there is a mixture of improvement and degradation. In fact, we find low
correlation not only between $\bar{h}$ and the performance metrics across
number of filters used, we also find low correlation between the improvement
with $\bar{h}$ and the improvement in photo-$z$ for individual objects when
morphology is added. We also do not see significant correlation between the
improvement of $h$ and $\Theta$ either.

The motivation to study the change in $\bar{h}$ was in fact to see if
morphology could decrease the degeneracy of multiple peaks, making only one
peak stand out to obtain a more accurate photo-$z$. So to probe this a little
further, we tabulated the distribution of $h$ for each run. From the
distribution of PDF heights, we find that the shift in the peak of the $h$
distribution is in fact very small, and this is in contrast with the change in
$w_{68}$ and $\Theta$. From further inspection of individual PDFs, we also
find that many PDFs have very fuzzy and noisy distributions, some even having
more than $10$ peaks in a single distribution. We suggest that these two
factors have inhibited $\bar{h}$ from becoming a viable indicator for
improvement in $p(z)$, and could be improved if smoother $p(z)$’s are
produced.

##  IV Conclusion and Future Work

From our study, it is clear that $\rho_{\textrm{PIT}}$ is not a good metric to
study improvement / degradation of the $p(z)$ in the context of CS82, although
it remains an important metric to measure over- and under-confidences in PDFs.
$\rho_{\textrm{CRPS}}$, $\bar{\Theta}$ and $\bar{w}_{68}$ are shown to be
promising metrics to evaluate improvements in the photo-$z$ PDFs reflected by
the quality of point estimates. The viability of the metric $\bar{h}$ remains
to be verified, and methods to produce smoother $p(z)$’s will be explored to
achieve this purpose.

Note that in this work we have assumed that an improvement in the photo-$z$
estimates implies an improvement in the $p(z)$ and $n(z)$, and this assumption
will be analysed in future work. Other future work include studies of $QQ$
plots, testing on improvements without relying on galaxy morphology, PDF
smoothing methods and also the exploration of other metrics.

###### Acknowledgements.

JYHS acknowledges the financial support from the MyBrainSc Scholarship endowed
by the Ministry of Education, Malaysia during which this work was completed.
JYHS would also like to thank Ofer Lahav, Samuel Schmidt, Alex Malz and other
members of the Large Synoptic Survey Telescope (LSST) Photo-$z$ Working Group
for fruitful discussions which led to this work.

## References

  * Fernández-Soto  _et al._ [2002] A. Fernández-Soto, K. M. Lanzetta, H.-W. Chen, B. Levine, and N. Yahata, MNRAS 330, 889 (2002).
  * Polsterer  _et al._ [2016] K. L. Polsterer, A. D’Isanto, and F. Gieseke, arXiv e-prints (2016), 1608.08016 .
  * Gerdes  _et al._ [2010] D. W. Gerdes, A. J. Sypniewski, T. A. McKay, J. Hao, M. R. Weis, R. H. Wechsler, and M. T. Busha, ApJ 715, 823 (2010).
  * Bonnett [2015] C. Bonnett, MNRAS 449, 1043 (2015).
  * Wittman  _et al._ [2016] D. M. Wittman, R. Bhaskar, and R. Tobin, MNRAS 457, 4005 (2016).
  * Schmidt  _et al._ [prep] S. J. Schmidt, A. I. Malz, J. Y. H. Soo, I. A. Almosallam, M. Brescia, S. Cavuoti, J. Cohen-Tanugi, A. J. Connolly, _et al._ , (in prep.).
  * Soo  _et al._ [2018] J. Y. H. Soo, B. Moraes, B. Joachimi, W. Hartley, O. Lahav, A. Charbonnier, M. Makler, M. E. S. Pereira, _et al._ , MNRAS 475, 3613 (2018).
  * Annis  _et al._ [2014] J. Annis, M. Soares-Santos, M. A. Strauss, A. C. Becker, S. Dodelson, X. Fan, J. E. Gunn, J. Hao, _et al._ , ApJ 794, 120 (2014).
  * Moraes  _et al._ [4 10] B. Moraes, J.-P. Kneib, A. Leauthaud, M. Makler, L. Van Waerbeke, K. Bundy, T. Erben, C. Heymans, _et al._ , in  _Revista Mexicana de Astronomia y Astrofisica Conference Series_, Revista Mexicana de Astronomia y Astrofisica, vol. 27, Vol. 44 (2014-10) pp. 202–203.
  * York  _et al._ [2000] D. G. York, J. Adelman, J. E. J. Anderson, S. F. Anderson, J. Annis, N. A. Bahcall, J. A. Bakken, R. Barkhouser, _et al._ , AJ 120, 1579 (2000).
  * Newman  _et al._ [2013] J. A. Newman, M. C. Cooper, M. Davis, S. M. Faber, A. L. Coil, P. Guhathakurta, D. C. Koo, A. Phillips, _et al._ , ApJS 208, 5 (2013).
  * Drinkwater  _et al._ [2010] M. J. Drinkwater, R. J. Jurek, C. Blake, D. Woods, K. Pimbblet, K. Glazebrook, R. Sharp, M. B. Pracy, _et al._ , MNRAS 401, 1429 (2010).
  * Le Fèvre  _et al._ [2013] O. Le Fèvre, P. Cassata, O. Cucciati, B. Garilli, O. Ilbert, V. Le Brun, D. Maccagni, C. Moreau, _et al._ , A&A 559, 21 (2013).
  * Sadeh  _et al._ [2016] I. Sadeh, F. B. Abdalla, and O. Lahav, PASP 128, 104502 (2016).


# Integer flows on triangularly connected signed graphs

Liangchen Li
School of Mathematical Sciences
Luoyang Normal University
Luoyang 471934, China
Email<EMAIL_ADDRESS>
Chong Li
Mathematics and Computer Science
Southern Arkansas University
100 E. University, Magnolia, Arkansas 71753-5000
Email<EMAIL_ADDRESS>
Rong Luo, Cun-Quan Zhang
Department of Mathematics
West Virginia University
Morgantown, WV 26505, USA
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>Partially supported by NSFC
(No. 12271438), Basic Research Foundation of Henan Educational Committee (No.
20ZX004)Partially supported by a grant from Simons Foundation (No.
839830)Partially supported by an NSF grant DMS-1700218

###### Abstract

A triangle-path in a graph $G$ is a sequence of distinct triangles
$T_{1},T_{2},\ldots,T_{m}$ in $G$ such that for any $i,j$ with $1\leq i<j\leq
m$, $|E(T_{i})\cap E(T_{i+1})|=1$ and $E(T_{i})\cap E(T_{j})=\emptyset$ if
$j>i+1$. A connected graph $G$ is triangularly connected if for any two
nonparallel edges $e$ and $e^{\prime}$ there is a triangle-path
$T_{1}T_{2}\cdots T_{m}$ such that $e\in E(T_{1})$ and $e^{\prime}\in
E(T_{m})$. For ordinary graphs, Fan et al. (J. Combin. Theory Ser. B 98 (2008)
1325-1336) characterize all triangularly connected graphs that admit nowhere-
zero $3$-flows or $4$-flows. Corollaries of this result include integer flow
of some families of ordinary graphs, such as, locally connected graphs due to
Lai (J. Graph Theory 42 (2003) 211-219) and some types of products of graphs
due to Imrich et al.(J. Graph Theory 64 (2010) 267-276). In this paper, Fan’s
result for triangularly connected graphs is further extended to signed graphs.
We proved that a flow-admissible triangularly connected signed graph admits a
nowhere-zero $4$-flow if and only if it is not the wheel $W_{5}$ associated
with a specific signature. Moreover, this result is sharp since there are
infinitely many unbalanced triangularly connected signed graphs admitting a
nowhere-zero $4$-flow but no $3$-flow.

Keywords: Signed graph; nowhere-zero flows; triangularly connected.

##  1 Introduction

Graphs or signed graphs in this paper are finite and may have loops and
parallel edges. For terminology and notations not defined here we follow [1,
3, 21].

The theory of integer flows which is a dual problem to the vertex coloring of
planar graphs was introduced by Tutte [18, 19]. Tutte’s flow theory has been
extended to signed graphs [2]. The concept of integer flows on signed graphs
naturally comes from the study of graphs embedded on nonorientable surfaces,
where nowhere-zero flow emerges as the dual of local tension. Bouchet [2] in
1983 proposed the following conjecture.

######  Conjecture 1.1.

(Bouchet [2]) Every flow-admissible signed graph admits a nowhere-zero
$6$-flow.

The best result toward Conjecture 1.1 is due to DeVos et al. [5] who prove
that the conjecture is true with $6$ replaced by $11$. Integer flows on signed
graphs also have been studied for many specific families of graphs. For more
details, the readers are refereed to [7, 10, 11, 13, 14, 15, 16, 20, 22].

In this paper, we investigate nowhere-zero integer flows in triangularly
connected signed graphs. For triangularly connected ordinary graphs, Fan et
al. [6] show that every triangularly connected ordinary graph admits a
nowhere-zero $4$-flow and they also characterize all such graphs not admitting
a nowhere-zero $3$-flow. For its signed counterpart, we prove the following
result.

######  Theorem 1.2.

If $(G,\sigma)$ is a flow-admissible triangularly connected signed graph, then
$(G,\sigma)$ admits a nowhere-zero $4$-flow if and only if
$(G,\sigma)\neq(W_{5},\sigma^{*})$ where $(W_{5},\sigma^{*})$ is the signed
graph in Figure 1. Moreover there are infinitely many triangularly connected
unbalanced signed graphs that admit a nowhere-zero $4$-flow but no $3$-flow.

Figure 1: $(W_{5},\sigma^{*})$ has a 5-NZF but no 4-NZF. Dotted edges are
negative.

A graph is locally connected if the subgraph induced by the neighbor of each
vertex is connected. It is known that locally connected graphs, square of
graphs, chordal graphs, triangulations on surfaces, and some types of products
of graphs are triangularly connected (such as [8], [9], for ordinary graphs)
and thus we have the following corollary.

######  Corollary 1.3.

Let $(G,\sigma)$ be a flow-admissible signed graph. If $G$ is locally
connected, then $(G,\sigma)$ admits a nowhere-zero $4$-flow if and only if
$(G,\sigma)\neq(W_{5},\sigma^{*})$. In particular, if $G$ is the square of a
connected graph or is the strong product of graphs, then $(G,\sigma)$ admits a
nowhere-zero $4$-flow.

It is worth to pointing out that in the study of flows of ordinary graphs,
Tutte’s result on the equivalence of modulo flows and integer flows serves as
one of most powerful tools (see [19]). However this equivalence no longer
holds for signed graphs. Therefore the approach in the proof of our theorem is
significantly different and difficult comparing with that of its ordinary
counterpart.

The rest of the paper is organized as follows: Basic notations and definitions
will be introduced in Section 2. Section 3 will present some lemmas needed in
the proofs of the main result. In Section 4, we will present a family of
unbalanced triangularly connected graphs that admit nowhere-zero $4$-flows but
no $3$-flows. The proof of Theorem 1.2 will be presented in Section 5.

##  2 Notations and Terminology

A triangle-path of length $m$, denoted by $T_{1}T_{2}\cdots T_{m}$ in $G$ is a
sequence of distinct triangles $T_{1},T_{2},\dots,T_{m}$ in $G$ such that for
any $1\leq i<j\leq m$,

$|E(T_{i})\cap E(T_{i+1})|=1\mbox{ and }E(T_{i})\cap E(T_{j})=\emptyset\mbox{
if }j>i+1.$

A connected graph $G$ is triangularly connected if for any two nonparallel
distinct edges $e$ and $e^{\prime}$, there is a triangle-path
$T_{1}T_{2}\cdots T_{m}$ such that $e\in E(T_{1})$ and $e^{\prime}\in
E(T_{m})$. Trivially, the graph with a single edge is triangularly connected.
Let $H_{1},H_{2},\dots,H_{t}$ be subgraphs of $G$. Denote by $H_{1}\triangle
H_{2}\triangle\cdots\triangle H_{t}$ the symmetric difference of those
subgraphs.

Let $G$ be a graph. Let $U_{1}$ and $U_{2}$ be two disjoint vertex sets.
Denote by $\delta_{G}(U_{1},U_{2})$ the set of edges with one end in $U_{1}$
and the other in $U_{2}$. For convenience, we write $\delta_{G}(U_{1})$ for
$\delta_{G}(U_{1},V(G)\setminus U_{1})$. We use $B(G)$ to denote the set of
bridges of $G$. A path in $G$ is said to be a _subdivided edge_ of $G$ if
every internal vertex of $P$ has degree $2$.

A _signed graph_ $(G,\sigma)$ is a graph $G$ together with a signature
$\sigma:E(G)\to\\{-1,1\\}$. An edge $e\in E(G)$ is _positive_ if $\sigma(e)=1$
and _negative_ otherwise. Denote the set of all negative edges of $(G,\sigma)$
by $E_{N}(G,\sigma)$ (or simply $E_{N}(G))$. For a vertex $v$ in $G$, we
define a new signature $\sigma^{\prime}$ by changing
$\sigma^{\prime}(e)=-\sigma(e)$ for each $e\in\delta_{G}(v)$. We say that
$\sigma^{\prime}$ is obtained from $\sigma$ by making a _switch_ at the vertex
$v$. Two signatures are said to be equivalent if one can be obtained from the
other by making a sequence of switch operations.

For convenience, the signature $\sigma$ is usually omitted if no confusion
arises or is written as $\sigma_{G}$ if it needs to emphasize $G$. For a
subgraph $H$ of $G$, denote by $(H,\sigma|_{H})$ the signed graph where
$\sigma|_{H}$ is the restriction of $\sigma$ on $E(H)$. If there is no
confusion from the context, we simply use $H$ to denote the signed subgraph.

Every edge of $G$ is composed of two half-edges $h$ and $\hat{h}$, each of
which is incident with one end. Denote the set of half-edges of $G$ by $H(G)$
and the set of half-edges incident with $v$ by $H_{G}(v)$. For a half-edge
$h\in H(G)$, we use $e_{h}$ to refer to the edge containing $h$. An
orientation of a signed graph $(G,\sigma)$ is a mapping
$\tau:H(G)\to\\{-1,1\\}$ such that $\tau(h)\tau(\hat{h})=-\sigma(e_{h})$ for
each $h\in H(G)$. It is convenient to consider $\tau$ as an assignment of
orientations on $H(G)$. Namely, if $\tau(h)=1$, $h$ is a half-edge oriented
away from its end and otherwise towards its end. Such an ordered pair
$(G,\tau)$ is called a bidirected graph.

######  Definition 2.1.

Let $(G,\tau)$ be a bidirected graph, $A$ be an abelian group, and $f:E(G)\to
A$ be a mapping. The pair $(\tau,f)$ (or to simplify, $f$) is an _$A$ -flow_
of $G$ if $\sum_{h\in H_{G}(v)}\tau(h)f(e_{h})=0$ for each $v\in V(G)$, and is
an (integer) _$k$ -flow_ if it is a $\mathbb{Z}$-flow and $|f(e)|<k$ for each
$e\in E(G)$.

Let $f$ be a flow of a signed graph $G$. The support of $f$, denoted by
$\operatorname{{\rm supp}}(f)$, is the set of edges $e$ with $f(e)\neq 0$. The
flow $f$ is nowhere-zero if $\operatorname{{\rm supp}}(f)=E(G)$. For
convenience, we abbreviate the notions of nowhere-zero $A$-flow and nowhere-
zero $k$-flow as $A$-NZF and $k$-NZF, respectively. Observe that $G$ admits an
$A$-NZF (resp., a $k$-NZF) under an orientation $\tau$ if and only if it
admits an $A$-NZF (resp., a $k$-NZF) under any orientation $\tau^{\prime}$. A
$\mathbb{Z}_{k}$-flow is also called a modulo $k$-flow. For an integer flow
$f$ of $G$ and a positive integer $t$, let $E_{f=\pm t}=\\{e\in
E(G):|f(e)|=t\\}$. For any subgraph $H$ of $G$, denote $f(H)=\\{f(e):e\in
E(H)\\}$.

A circuit is _balanced_ if it contains an even number of negative edges, and
is _unbalanced_ otherwise. A signed graph is called balanced if it contains no
unbalanced circuit and is called _unbalanced_ otherwise. A balanced signed
graph is equivalent to an ordinary graph. A signed circuit is defined as a
signed graph of one of the following three types:

(1) a balanced circuit;

(2) a short barbell, the union of two unbalanced circuits that meet at a
single vertex;

(3) a long barbell, the union of two vertex-disjoint unbalanced circuits with
a path with at least one edge that meets the circuits only at its ends.

######  Proposition 2.2.

([2]) Every balanced circuit or short barbell has a $2$-NZF and every long
barbell has a $3$-NZF where an edge has flow value $2$ or $-2$ if and only if
it belongs to the path connecting the two unbalanced circuits.

A signed graph $G$ is flow-admissible if it admits a $k$-NZF for some positive
integer $k$. Bouchet [2] characterized all flow-admissible signed graphs as
follows.

######  Proposition 2.3.

([2]) Let $(G,\sigma)$ be a connected signed graph. The following three
statements are equivalent:

(1) $(G,\sigma)$ is flow-admissible;

(2) $(G,\sigma)$ is not equivalent to a signed graph with exactly one negative
edge and it has no cut-edge $b$ such that $(G-b,\sigma|_{G-b})$ has a balanced
component;

(3) every edge in $(G,\sigma)$ is contained in a signed circuit.

##  3 Lemmas

In this section, we will present some lemmas that will be used in the proof of
our main result.

Let $H$ be a signed graph and $C$ be a balanced circuit. Define the following
operation:

$\Phi_{2}\mbox{-operation}:\mbox{ add a balanced circuit $C$ to $H$ if
$|E(C)\setminus E(H)|\leq 2$.}$

Let $H$ be a subgraph of $G$. We use $\langle H\rangle_{2}$ to denote the
maximal subgraph of $G$ obtained from $H$ via $\Phi_{2}$-operations. Zýka [24]
proved the following result.

######  Lemma 3.1.

(Zýka [24]) Let $(G,\sigma)$ be a signed graph and $H$ be a subgraph of $G$.
If $\langle H\rangle_{2}=(G,\sigma)$, then $(G,\sigma)$ admits a
$\mathbb{Z}_{3}$-flow $\phi$ such that $E(G)\setminus
E(H)\subseteq\operatorname{{\rm supp}}(\phi)$.

######  Lemma 3.2.

Let $(G,\sigma)$ be a triangularly connected signed graph. Let $T$ be an
unbalanced triangle if there is one otherwise let $T$ be any balanced
triangle. Then $\langle T\rangle_{2}=(G,\sigma)$ and $(G,\sigma)$ has a
$\operatorname{\mathbb{Z}}_{3}$-flow $\phi$ such that $E_{\phi=0}\subseteq
E(T)$ and for any triangle $T^{\prime}$, if there are two edges
$e_{1},e_{2}\in E(T^{\prime})$ such that $T^{\prime}$ is the only triangle
containing them, then $\phi(e_{1})=\phi(e_{2})$.

###### Proof.

If there is a triangle $T^{\prime}$ containing two edges $uv,uw$ such that
each is contained in exactly one triangle which is $T^{\prime}$, then split
$u$ into two vertices $u_{1}$ and $u_{2}$ such that $u_{1}$ is adjacent to $v$
and $w$, and $u_{2}$ is adjacent to each vertex in $N_{G}(u)-\\{v,w\\}$. Then
the degree of $u_{1}$ is $2$. Repeating this operation until every pair of
such edges share a degree $2$-vertex. Denote the resulting graph by
$(G^{\prime},\sigma)$.

It is clear that $\langle T\rangle_{2}=(G^{\prime},\sigma)$. Thus by Lemma
3.1, $(G^{\prime},\sigma)$ has a $\operatorname{\mathbb{Z}}_{3}$-flow $\phi$
such that $E_{\phi=0}\subseteq E(T)$. Then $\phi$ is a desired
$\operatorname{\mathbb{Z}}_{3}$-flow of $(G,\sigma)$. ∎

######  Lemma 3.3.

(Xu and Zhang [23]) A signed graph $(G,\sigma)$ admits a $2$-NZF if and only
if each component of $(G,\sigma)$ is eulerian and has an even number of
negative edges.

The following two lemmas strengthen a result due to Xu and Zhang [23].

######  Lemma 3.4.

(DeVos et al. [5]) Let $(G,\sigma)$ be a bridgeless signed graph admitting a
$\mathbb{Z}_{3}$\- NZF. Then for any edge $e^{\prime}\in E(G)$ and for any
$i\in\\{1,2\\}$, $(G,\sigma)$ admits a $3$-NZF $f$ such that
$f(e^{\prime})=i$.

The next lemma is proved in [12]. For the purpose of self-conaintment, we
include their proof here.

######  Lemma 3.5.

Let $(G,\sigma)$ be a signed graph such that there is a path containing all
the bridges. Then $(G,\sigma)$ admits a $3$-NZF if $(G,\sigma)$ admits a
$\mathbb{Z}_{3}$-NZF.

###### Proof.

Let $(\tau,\phi)$ be a nowhere-zero $\mathbb{Z}_{3}$-flow of $(G,\sigma)$. We
may assume $\phi(e)=1$ for each edge $e$. By Lemma 3.3, we may further assume
that $G$ has bridges. Since there is a path containing all the bridges, $G$
has exactly two leaf blocks, say $G_{1}$ and $G_{2}$. Let $e_{1}=u_{1}v_{1}$
and $e_{2}=u_{2}v_{2}$ be the two bridges such that $u_{i}\in V(G_{i})$ for
each $i=1,2$.

For each $i=1,2$, denote by $G_{i}^{\prime}$ the signed graph obtained from
$G_{i}$ by adding a negative loop $e_{i}^{\prime}$ at $u_{i}$ such that the
two half edges of $e_{i}^{\prime}$ are oriented the same as the half edge of
$e_{i}$ incident with $u_{i}$. Then both $G_{1}$ and $G_{2}$ are bridgeless
and each admits a $\mathbb{Z}_{3}$-NZF. By Lemma 3.4, $G_{i}^{\prime}$ admits
a nowhere-zero $3$-flow $g_{i}$ such that $g(e_{i})=1$ for each $i=1,2$

If $e_{1}$ and $e_{2}$ are distinct, denote by $G_{3}^{\prime}$ the signed
graph obtained by deleting $G_{1}$, $G_{2}$, $e_{1}$ and $e_{2}$, and then
adding a new edge $e_{3}=v_{1}v_{2}$ where $v_{1}v_{2}$ consists of the half-
edge of $e_{1}$ incident with $v_{1}$ with the same orientation and the half-
edge of $e_{2}$ incident with $v_{2}$ with the same orientation. Then $G_{3}$
is bridgeless and admits a $\mathbb{Z}_{3}$-NZF. By Lemma 3.4, $G_{3}$ admits
a nowhere-zero $3$-flow $g_{3}$ such that $g(e_{3})=2$.

If $e_{1}=e_{2}$, then $e_{1}$ is the only bridge of $G$ and thus $G=G_{1}\cup
G_{2}\cup\\{e_{1}\\}$. It is easy to see that one can obtain a $3$-NZF of
$(G,\sigma)$ from $g_{1}$ and $g_{2}$ by deleting the negative loops
$e_{1}^{\prime},e_{2}^{\prime}$ and assigning $e_{1}$ with the flow value $2$,
a contradiction

If $e_{1}\not=e_{2}$, one can merge $g_{1},g_{2}$ and $g_{3}$ to obtain a
nowhere-zero $3$-flow of $(G,\sigma)$, a contradiction. This completes the
proof of the lemma. ∎

The following lemma directly follows from the definition of triangularly
connected graphs.

######  Lemma 3.6.

Let $G$ be a triangularly connected graph and $U,W$ be two disjoint vertex set
with $|\delta_{G}(U,W)|=3$. Then either the three edges in $\delta_{G}(U,W)$
share a common end vertex or the three edges induce a path on four vertices.
Moreover in the latter case, the four vertices of the path induce a $K_{4}$
minus one edge.

$y_{1}$$x_{1}$$y_{2}$$y_{3}$$x_{2}$$x_{3}$$H_{2}$$H_{3}$$H_{1}$$H_{0}$ Figure
2: The structure of a graph with three bridges not contained in a path

######  Lemma 3.7.

Let $G$ be a triangularly connected graph with $\delta(G)\geq 3$ and $E_{0}$
be a set of edges of $G$. If $|E_{0}|\leq 4$ and each component of $G-E_{0}$
is either an isolated vertex or has minimum degree at least 2, then in each
nontrivial component, there is a path containing all the bridges of the
component.

###### Proof.

Suppose to the contrary that $G^{\prime}=G-E_{0}$ has a component say $H$ that
contains three bridges, say $x_{1}y_{1},x_{2}y_{2},x_{3}y_{3}$, which don’t
belong to a path (see Figure 2). Deleting these three edges, we will get four
components and denote the component containing $x_{i}$ by $H_{i}$ for
$i=1,2,3$ and denote the component containing $y_{1},y_{2},y_{3}$ by $H_{0}$.

Since $G$ is triangularly connected and $\delta(G)\geq 3$, $G$ has no cut-
vertex and has no $2$-edge-cut. Thus $G$ is $3$-edge connected. Since the
minimum degree of each nontrivial component of $G-E_{0}$ is at least $2$,
$|V(H_{i})|\geq 2$ for each $i=1,2,3$.

######  Claim 3.7.1.

$G^{\prime}$ is connected.

_Proof._ Suppose to the contrary that $G_{1}$ and $G_{2}$ are two components
of $G^{\prime}$, where $H_{i}\subseteq G_{1}$ for each $i=1,2,3$. This implies
that
$2|E_{0}|=|\delta_{G}(G_{2})|+\sum_{i=0}^{3}|\delta_{G}(V(H_{i}))|-3\times
2\geq 9$. It contradicts the hypothesis $|E_{0}|\leq 4$. $\square$

######  Claim 3.7.2.

There exists an integer $i\in\\{1,2,3\\}$ such that $\delta_{G}(H_{i})=3$ and
for any $H_{j}$ with $|\delta_{G}(H_{j})|=3$,
$\delta_{G}(H_{j})\neq\delta_{G}(H_{j},H_{0}).$

_Proof._ We first prove that there exists an $i\in\\{1,2,3\\}$ such that
$\delta_{G}(H_{i})=3$. Suppose to the contrary that $\delta(H_{j})\geq 4$ for
each $j\in\\{1,2,3\\}$. It follows that
$2|E_{0}|=\sum_{j=1}^{3}|\delta_{G}(H_{j})|+|\delta_{G}(H_{0})|-3\times 2\geq
3\times 4+3-6=9$, a contradiction.

Without loss of generality, assume that $|\delta_{G}(H_{1})|=3$. Suppose to
the contrary that $\delta_{G}(H_{1})=\delta_{G}(H_{1},H_{0})$. It follows that
$|\delta_{G}(H_{2})|=|\delta_{G}(H_{3})|=3$, otherwise
$2|E_{0}|=\sum_{j=1}^{3}|\delta_{G}(H_{j})|+|\delta_{G}(H_{0})|-3\times 2\geq
9$, a contradiction. If $|\delta_{G}(H_{2})\cap\delta_{G}(H_{3})|\leq 1$, then
$|E_{0}|\geq\sum_{j=1}^{3}(|\delta_{G}(H_{j})|-1)-1\geq 5$, a contradiction.
Thus $|\delta_{G}(H_{2})\cap\delta_{G}(H_{3})|=2$. This implies that
$\\{x_{2}y_{2},x_{3}y_{3}\\}$ is a 2-edge-cut of $G$. It contradicts that $G$
is 3-edge-connected. Therefore
$\delta_{G}(H_{1})\not=\delta_{G}(H_{1},H_{0})$. This completes the proof of
this claim. $\square$

By Claim 3.7.2, in the following without loss of generality we assume that
$|\delta_{G}(H_{1})|=3$ and $\delta_{G}(H_{1},H_{2})\not=\emptyset$.

######  Claim 3.7.3.

$\delta_{G}(H_{1},H_{3})=\emptyset$, $|\delta_{G}(H_{3})|=3$, and
$\delta_{G}(H_{2},H_{0})=\\{x_{2}y_{2}\\}$.

_Proof._ Suppose to the contrary that $\delta_{G}(H_{1},H_{3})\not=\emptyset$.
Since $\delta_{G}(H_{1},H_{2})\not=\emptyset$, by Claim 3.7.2, we have
$|\delta_{G}(H_{1},H_{i})|=1$ for each $i=0,2,3$. Since $\delta_{G}(H_{1})$ is
an edge cut with $|\delta_{G}(H_{1})|=3$ and clearly the three edges in
$\delta_{G}(H_{1})$ don’t induce a path, by Lemma 3.6, the three edges share a
common end vertex which is $x_{1}$. Since $|V(H_{1})|\geq 2$, we have that
$x_{1}$ is a cut-vertex, a contradiction. This proves
$\delta_{G}(H_{1},H_{3})=\emptyset$.

Since $\delta_{G}(H_{1},H_{3})=\emptyset$ and $|E_{0}|\leq 4$, we have
$3\leq|\delta_{G}(H_{3})|\leq 4-2+1=3$. Thus $|\delta_{G}(H_{3})|=3$.

Since
$(\delta_{G}(H_{1})\cup\delta_{G}(H_{3}))\setminus\\{x_{1}y_{1},x_{3}y_{3}\\}\subseteq
E_{0}$ and
$|(\delta_{G}(H_{1})\cup\delta_{G}(H_{3}))\setminus\\{x_{1}y_{1},x_{3}y_{3}\\}|=4$,
we have
$(\delta_{G}(H_{1})\cup\delta_{G}(H_{3}))\setminus\\{x_{1}y_{1},x_{3}y_{3}\\}=E_{0}$.
Therefore $\delta_{G}(H_{2},H_{0})=\\{x_{2}y_{2}\\}$. $\square$

The final step. By Claims 3.7.2 and 3.7.3, there is an edge
$u_{1}u_{2}\in\delta_{G}(H_{1},H_{2})$ where $u_{1}\in V(H_{1})$ and
$u_{1}\not=x_{1}$. By Lemma 3.6, $u_{2}$ and $y_{1}$ are adjacent. Since
$\delta_{G}(H_{2},H_{0})=\\{x_{2}y_{2}\\}$ by Claim 3.7.3, we have
$u_{2}=x_{2}$ and $y_{1}=y_{2}$. Similarly there is an edge
$v_{3}v_{2}\in\delta_{G}(H_{3},H_{2})$ where $v_{3}\in V(H_{3})$ and
$v_{3}\not=x_{3}$ and $v_{2}=x_{2}$. By Lemma 3.6, all the edges in
$\delta_{G}(H_{2})$ share a common end vertex $x_{2}$. Since $|V(H_{2})|\geq
2$, $x_{2}$ is a cut-vertex, a contradiction to the fact that $G$ has no cut-
vertex. This contradiction completes the proof of the lemma. ∎

The following is a corollary of Lemmas 3.5 and 3.7.

######  Lemma 3.8.

Let $(G,\sigma)$ be a triangularly connected signed graph and $\phi$ be a
$\mathbb{Z}_{3}$-flow of $(G,\sigma)$ with $|E_{\phi=0}|\leq 4$, then
$(G,\sigma)$ admits a $3$-flow $f$ with $\operatorname{{\rm
supp}}(f)=\operatorname{{\rm supp}}(\phi)$.

######  Lemma 3.9.

Let $k\geq 3$ be an integer and $C$ be a balanced circuit of $(G,\sigma)$. Let
$g$ be a $2$-flow of $(G,\sigma)$ with $\operatorname{{\rm supp}}(g)=E(C)$ and
$f_{1}$ be an integer $k$-flow of $(G,\sigma)$ such that $|\operatorname{{\rm
supp}}(f_{1})\cap E(C)|\leq k-2$ and $|f_{1}(e)|\leq\frac{k}{2}$ for each
$e\in E(C)$. Then there is an $\alpha\in\\{\pm 1,\pm
2,\cdots,\pm\lfloor\frac{k}{2}\rfloor\\}$ such that $f_{2}=f_{1}-\alpha g$ is
an integer $k$-flow with $\operatorname{{\rm supp}}(f_{2})=\operatorname{{\rm
supp}}(f_{1})\cup E(C)$.

###### Proof.

Since $|\operatorname{{\rm supp}}(f_{1})\cap E(C)|\leq k-2$, we have
$|f_{1}(C)|\leq k-1$.

If $k$ is odd, then there exists an integer $\alpha\in\\{\pm
1,\dots,\pm\lfloor\frac{k}{2}\rfloor\\}\setminus f_{1}(C)$.

If $k$ is even, then there exists at least two integers in $\\{\pm
1,\dots,\pm\frac{k}{2}\\}\setminus f_{1}(C)$. If $\\{\pm\frac{k}{2}\\}\cap
f_{1}(C)=\emptyset$, let $\alpha=\frac{k}{2}$; otherwise pick one
$\alpha\in\\{\pm 1,\cdots,\pm(\frac{k}{2}-1)\\}\setminus f_{1}(C)$. Let
$f_{2}=f_{1}-\alpha g$.

Clearly, when $|\alpha|<\frac{k}{2}$, $f_{2}$ is an integer $k$-flow with
$\operatorname{{\rm supp}}(f_{2})=\operatorname{{\rm supp}}(f_{1})\cup E(C)$.

If $\alpha=\frac{k}{2}$, then $\\{\pm\frac{k}{2}\\}\cap f_{1}(C)=\emptyset$.
Thus for each $e\in E(C)$, $|f_{1}(e)|\leq\frac{k}{2}-1$, so $-(k-1)\leq
f_{2}(e)=f_{1}(e)-\alpha g(e)\leq k-1$ and $f_{2}(e)\not=0$. Therefore,
$f_{2}$ is an integer $k$-flow with $\operatorname{{\rm
supp}}(f_{2})=\operatorname{{\rm supp}}(f_{1})\cup E(C)$. This completes the
proof of the lemma. ∎

######  Lemma 3.10.

Let $C$ be a balanced circuit of $(G,\sigma)$ with length at most $4$ and $g$
be a $2$-flow of $(G,\sigma)$ with $\operatorname{{\rm supp}}(g_{1})=E(C)$.
Then for any $\mathbb{Z}_{3}$-flow $\phi$ of $(G,\sigma)$, there is an
$\alpha\in\mathbb{Z}_{3}$ such that $\phi_{1}=\phi-\alpha g$ is a
$\mathbb{Z}_{3}$-flow satisfying $|E_{\phi_{1}=0}\cap
E(C)|\in\\{0,|E(C)|-2\\}$.

###### Proof.

Let $\phi$ be a $\mathbb{Z}_{3}$-flow of $(G,\sigma)$. If $|E_{\phi=0}\cap
E(C)|\in\\{0,|E(C)|-2\\}$, take $\alpha=0$.

If $|E_{\phi=0}\cap E(C)|\geq|E(C)|-1$, we can easily find some
$\alpha\in\mathbb{Z}_{3}$ such that $\phi_{1}=\phi-\alpha g_{1}$ is a
$\mathbb{Z}_{3}$-flow satisfying $|E_{\phi_{1}=0}\cap E(C)|=0$.

Now we assume $|E_{\phi=0}\cap E(C)|\leq|E(C)|-3$ and $|E_{\phi_{1}=0}\cap
E(C)|\not\in\\{0,|E(C)|-2\\}$. Then $|E(C)|=4$ and $|E_{\phi=0}\cap
E(C)|=|E(C)|-3=1$. Thus $|\phi(C)|\in\\{2,3\\}$. If $|\phi(C)|=2$, then choose
an $\alpha$ in $\mathbb{Z}_{3}\setminus\phi(C)$. If $|\phi(C)|=3$, then there
is an $\alpha\in\phi(C)\setminus\\{0\\}$ such that there are exactly two edges
$e$ in $E(C)$ with $\phi(e)=\alpha$. Then $\phi_{1}=\phi-\alpha g$ is a
$\mathbb{Z}_{3}$-flow satisfying $\phi(e)=\phi_{1}(e)$ for each $e\in
E(G)-E(C)$ and $|E_{\phi_{1}=0}\cap E(C)|\in\\{0,|E(C)|-2\\}$. ∎

######  Lemma 3.11.

Let $(G,\sigma)$ be a triangularly connected signed graph and
$C_{1},\dots,C_{t}$ $(1\leq t\leq 2)$ be pairwise edge-disjoint balanced
circuits of length at most $4$. If $\phi$ is a $\mathbb{Z}_{3}$-flow of
$(G,\sigma)$ such that $E_{\phi=0}\subseteq\cup_{i=1}^{t}E(C_{i})$, then
$(G,\sigma)$ admits a $4$-NZF.

###### Proof.

By Lemma 3.10, we may assume that $|E_{\phi=0}\cap
E(C_{i})|\in\\{0,|E(C_{i})|-2\\}$ for each $i=1,\dots,t$. Then
$|E_{\phi=0}|\leq 4$. By Lemma 3.8, there is a $3$-flow $f$ such that
$\operatorname{{\rm supp}}(f)=\operatorname{{\rm supp}}(\phi)$ and of course
$f$ is a $4$-flow. Taking $k=4$, we have $|f(e)|\leq\frac{k}{2}$ and
$|E_{f\not=0}\cap E(C_{i})|=2=k-2$ for each $C_{i}$ with $E_{f=0}\cap
E(C_{i})\not=\emptyset$. Applying Lemma 3.9 on each $C_{i}$ with $E_{f=0}\cap
E(C_{i})\not=\emptyset$, one can obtain a desired $4$-NZF. ∎

By Lemma 2.2 of [6], the proof of the following lemma is straightforward.

######  Lemma 3.12.

Let $f$ be a $\mathbb{Z}_{3}$-flow of $(G,\sigma)$ and $H=T_{1}T_{2}\cdots
T_{m}$ be a triangle-path in $G$ such that each $T_{i}$ is balanced for $1\leq
i\leq m$. Given an edge $e_{0}\in E(H)$, then there is another
$\mathbb{Z}_{3}$-flow $g$ of $(G,\sigma)$ satisfying:

(1) $f(e)=g(e)$ for each $e\not\in E(H)$;

(2) $g(e)\not=0$ for each edge $e\in E(H)-\\{e_{0}\\}$.

######  Lemma 3.13.

Let $(G,\sigma)$ be a triangularly connected signed graph, $C_{1}$ be a
balanced triangle and $C_{2}$ be a balanced circuit of length at most $4$ such
that $|E(C_{1})\cap E(C_{2})|\leq 1$. If $\phi$ is a $\mathbb{Z}_{3}$-flow of
$G$ such that $E_{\phi=0}\subseteq E(C_{1})\cup E(C_{2})$, then $(G,\sigma)$
admits a $4$-NZF.

###### Proof.

If $C_{1}$ and $C_{2}$ are edge-disjoint, then by Lemma 3.11, $(G,\sigma)$
admits a $4$-NZF.

If $C_{1}$ and $C_{2}$ are not edge-disjoint, then $|E(C_{1})\cap
E(C_{2})|=1$. Let $e_{0}$ be the common edge of $C_{1}$ and $C_{2}$. Applying
Lemma 3.12 on $H=C_{1}$ and $e_{0}$, we may assume $E_{\phi=0}\subseteq
E(C_{2})$. By Lemma 3.11, $(G,\sigma)$ admits a $4$-NZF. ∎

##  4 Sharpness of Theorem 1.2

Fan et al. [6] give a complete characterization of triangularly connected
ordinary graphs that admit a $4$-NZF but no $3$-NZF. In this subsection we
present a family of unbalanced triangularly connected signed graphs that admit
a $4$-NZF but no $3$-NZF. Interestingly all those graphs do not contain an
unbalanced triangle. This indicates that there are unbalanced triangularly
connected signed graphs without unbalanced triangles.

For each integer $t\geq 4$, construct the signed graph $(G_{2t},\sigma)$ as
follows (see Figure 3 for an illustration with $t=4$):

(1) The graph $G_{2t}$ is constructed from the two circuits
$C_{1}=x_{1}x_{2}\cdots x_{t}x_{1}$ and $C_{2}=y_{1}y_{2}\cdots y_{t}y_{1}$ by
adding the edges $y_{i}x_{i}$ and $y_{i}x_{i+1}$ for each $i\in Z_{t}$;

(2) $E_{N}(G_{2t},\sigma)$ consists of the edges $x_{1}x_{2},y_{1}y_{2}$ and
all edges $y_{i}x_{i},y_{i}x_{i+1}$ except $y_{1}x_{2}$.

$x_{1}$$y_{1}$$x_{4}$$x_{3}$$x_{2}$$y_{2}$$y_{4}$$y_{3}$ Figure 3: an
unbalanced signed graph $(G_{8},\sigma)$

######  Theorem 4.1.

For each $t\geq 4$, $(G_{2t},\sigma)$ is flow-admissible and admits a $4$-NZF
but no $3$-NZF.

Since $(G_{2t},\sigma)$ is bridgeless and every edge is contained in a
balanced triangle, by Proposition 2.3, it is flow-admissible. Since $G_{2t}$
is Eulerian, the second part of Theorem 4.1 follows from the following result
due to Mačajova and Škoviera.

######  Theorem 4.2.

(Mačajova and Škoviera[15]) Let $(G,\sigma)$ be an Eulerian signed graph with
an odd number of negative edges. Then $(G,\sigma)$ admits a $4$-NZF if it is
flow-admissible. Moreover $(G,\sigma)$ admits a $3$-NZF if and only if
$(G,\sigma)$ can be decomposed into three signed Eulerian subgraphs that have
a vertex in common and that each has an odd number of negative edges.

##  5 Proof of Theorem 1.2

We prove Theorem 1.2 by contradiction. Let $(G,\sigma)$ be a counterexample
such that $\beta(G)=\sum_{v\in V(G)}(d(v)-2)$ is as small as possible. Let
$\tau$ be a fixed orientation of $(G,\sigma)$ in the proof.

Hu and Li [7] show that $(W_{5},\sigma^{*})$ in Figure 1 admits a $5$-NZF but
no $4$-NZF. Then $(G,\sigma)$ does not admit a $4$-NZF. By Lemma 3.11 we have
the following fact which will be applied frequently in the proof.

Fact A $(G,\sigma)$ does not admit a $\operatorname{\mathbb{Z}}_{3}$-flow
$\phi$ such that $E_{\phi=0}\subseteq E(C_{1})\cup\cdots\cup E(C_{t})$ where
$1\leq t\leq 2$ and $C_{1},\dots,C_{t}$ are edge-disjoint balanced circuits of
length at most four.

If $G$ contains two parallel edges $e_{1}$ and $e_{2}$, then after inserting a
degree $2$-vertex into $e_{1}$, the resulting graph $G^{\prime}$ remains
triangularly connected, flow-admissible, and $\beta(G^{\prime})=\beta(G)$.
Thus in the following proof, we assume that $G$ is simple.

If $G$ contains no unbalanced triangle, let $T$ be a triangle. By Lemma 3.2,
let $\phi$ be a $\mathbb{Z}_{3}$-flow $\phi$ with $E_{\phi=0}\subseteq E(T)$,
a contradiction to Fact A. Thus $G$ contains an unbalanced triangle.

(I) $(G,\sigma)$ contains two edge-disjoint unbalanced triangles.

Proof of (I). Suppose to the contrary that $(G,\sigma)$ contains no edge-
disjoint unbalanced triangles. Let $T$ be an unbalanced triangle and $\phi$ be
a $\mathbb{Z}_{3}$-flow $\phi$ with $E_{\phi=0}\subseteq E(T)$.

We consider two cases in the following.

Case I.1. $(G,\sigma)$ contains at least two unbalanced triangles.

Let $T_{1},T_{2},\dots,T_{t}$ be all the unbalanced triangles where $T=T_{1}$.
Then $t\geq 2$. Since $(G,\sigma)$ contains no edge-disjoint unbalanced
triangles, all unbalanced triangles share a common edge, denoted by $uv$. For
each $i$ denote by $w_{i}$ the third vertex of $T_{i}$. Then for any $1\leq
i<j\leq t$, $T_{i}\bigtriangleup T_{j}$ is a balanced circuit of length $4$.

Since $T_{1}\bigtriangleup T_{2}$ is a balanced $4$-circuit, by Fact A,
$\phi(uv)=0$ and $uv$ is not contained in a balanced triangle. This implies
that no other triangle than $T_{1},T_{2},\dots,T_{t}$ contains $uv$.

Since $(G,\sigma)$ is flow-admissible, there is a signed circuit $C$
containing $uv$. By Proposition 2.2, let $f$ be a $2$-flow (if $C$ is a
balanced circuit or a short barbell) or a $3$-flow (if $C$ is a long barbell)
such that $\operatorname{{\rm supp}}(f)=E(C)$. Let $\phi_{1}=\phi+f$ be the
$\mathbb{Z}_{3}$-flow. Then $\phi_{1}(uv)\not=0$.

Let $e\in E_{\phi_{1}=0}-\bigcup_{i=1}^{t}E(T_{i})$. Then there is a triangle-
path $S_{1}S_{2}\cdots S_{k}$ where $e\in S_{k}$, $uv\in
S_{1}\in\\{T_{1},T_{2},\dots,T_{t}\\}$, and $S_{2},S_{3},\dots,S_{k}$ are
balanced. Let $H=S_{2}S_{3}\cdots S_{k}$ and $e^{\prime}=E(S_{1})\cap
E(S_{2})$. By Lemma 3.12, there is a $\mathbb{Z}_{3}$-flow $g$ of $(G,\sigma)$
satisfying:

(1) $\phi_{1}(e)=g(e)$ for each $e\not\in E(H)$;

(2) $g(e)\not=0$ for each edge $e\in E(H)-\\{e^{\prime}\\}$.

By applying the above operation on each edge in
$E_{\phi_{1}=0}-\bigcup_{i=1}^{t}E(T_{i})$, one can obtain a
$\mathbb{Z}_{3}$-flow $\phi_{2}$ such that
$E_{\phi_{2}=0}\subseteq\bigcup_{i=1}^{t}E(T_{i})-\\{uv\\}$.

Denote $C_{i}=T_{1}\bigtriangleup T_{i}$ for each $i=2,\dots,t$. Then each
$C_{i}$ is a balanced $4$-circuit. For each $i=2,\dots,t$, let $f_{i}$ be a
$2$-flow of $(G,\sigma)$ with $\operatorname{{\rm supp}}(f_{i})=E(C_{i})$ and
let
$\alpha_{i}\in\mathbb{Z}_{3}-\\{\phi_{2}(uw_{i})f_{i}(uw_{i}),\phi_{2}(vw_{i})f_{i}(vw_{i})\\}$.
Let $\phi_{3}=\phi_{2}-\sum_{i=2}^{t}\alpha_{i}f_{i}$. Then $\phi_{3}$ is a
$\mathbb{Z}_{3}$-flow such that
$E_{\phi_{3}=0}\subseteq\\{uw_{1},vw_{1}\\}\subseteq E(C_{2})$, a
contradiction to Fact A.

Case I.2. $(G,\sigma)$ contains only one unbalanced triangle.

Denote $E(T)=\\{e_{1},e_{2},e_{3}\\}$. If every edge in $E_{\phi=0}$ is
contained in a triangle other than $T$, then every edge in $E_{\phi=0}$ is
contained in a balanced triangle since $T$ is the only unbalanced triangle in
$(G,\sigma)$. By Lemma 3.11, $|E_{\phi=0}|\geq 2$ and those balanced triangles
are not edge-disjoint. This implies that there is a $K_{4}$ containing $T$
where $T$ is the only unbalanced triangle in the $K_{4}$. However, $T$ is the
symmetric difference of the other three balanced triangles in the $K_{4}$.
Thus $T$ is balanced, a contradiction. Therefore there is one edge in
$E_{\phi=0}$ that is contained in only one triangle which is $T$.

Since $(G,\sigma)$ is flow-admissible, there is another edge in $E(T)$ which
is contained in a balanced triangle. Without loss generality, assume that
$e_{1}$ is contained in only one triangle, $\phi(e_{1})=0$ and $e_{3}$ is
contained a balanced triangle. Note that by Lemma 3.2, if $e_{2}$ is not
contained in a balanced triangle, then $\phi(e_{1})=\phi(e_{2})=0$.

Since $(G,\sigma)$ is flow-admissible, by Proposition 2.3, there is a signed
circuit $C_{1}$ containing $e_{1}$ and there is a signed circuit $C_{2}$
containing $e_{2}$. We choose $C_{2}=C_{1}$ if there is a signed circuit
containing both $e_{1}$ and $e_{2}$; otherwise choose any signed circuit
$C_{2}$ containing $e_{2}$.

By Lemma 2.2, let $f_{i}$ be a $2$-flow or $3$-flow of $(G,\sigma)$ with
$\operatorname{{\rm supp}}(f_{i})=E(C_{i})$ for each $i=1,2$.

We construct another $\operatorname{\mathbb{Z}}_{3}$-flow $\phi_{1}$ of
$(G,\sigma)$ as follows:

Let $\alpha\in\operatorname{\mathbb{Z}}_{3}-\\{0,\phi(e_{2})f_{2}(e_{2})\\}$.
If $C_{1}=C_{2}$, then $f_{1}=f_{2}$ and let $\phi_{1}=\phi-\alpha f_{1}$; if
$C_{1}\not=C_{2}$, then $f_{1}(e_{2})=f_{2}(e_{1})=0$ and let
$\phi_{1}=\phi-\alpha(f_{1}+f_{2})$.

Then $E_{\phi_{1}=0}\cap\\{e_{1},e_{2}\\}=\emptyset$ and every edge in
$E_{\phi_{1}=0}$ is contained in a balanced triangle. Similar to the argument
in Case I.1, there is a $\mathbb{Z}_{3}$-flow $\phi_{2}$ such that
$E_{\phi_{2}=0}\subseteq\\{e_{3}\\}$ if $e_{2}$ is not contained in a balanced
triangle or $E_{\phi_{2}=0}\subseteq\\{e_{2},e_{3}\\}$ otherwise, a
contradiction to Fact A.

We obtain a contradiction in either case and thus completes the proof of (I).
$\Box$

(II) $G$ is locally connected.

Proof of (II). Suppose to the contrary that $G$ is not locally connected. Then
there is a vertex $v\in V(G)$ such that $G[N_{G}(v)]$ is not connected. Since
$G$ is triangularly connected, each component of $G[N_{G}(v)]$ is nontrivial.
Let $H$ be a component of $G[N_{G}(v)]$. Split $v$ into two nonadjacent
vertices $v^{\prime}$ and $v^{\prime\prime}$ where $v^{\prime}$ is adjacent to
all vertices in $H$ and $v^{\prime\prime}$ is adjacent to all vertices in
$N_{G}(v)-V(H)$. The signs of all edges remain the same. Denote the resulting
signed graph by $(G^{\prime},\sigma)$. By (I), $(G^{\prime},\sigma)$ contains
two edge-disjoint unbalanced triangles. Since $G^{\prime}$ is connected and
bridgeless, by Proposition 2.3, $(G^{\prime},\sigma)$ is flow-admissible.
Obviously $\beta(G^{\prime})<\beta(G)$ and $G^{\prime}$ remains triangularly
connected. By the minimality of $\beta(G)$, $(G^{\prime},\sigma)$ admits a
4-NZF $f$. Identifying $v^{\prime}$ and $v^{\prime\prime}$, one can easily
obtain a 4-NZF of $(G,\sigma)$, a contradiction. Therefore $G$ is locally
connected. $\Box$

(III) $(G,\sigma)$ does not contain any of the $11$ configurations in Figure
4.

Proof of (III). For a balanced circuit or a short barbell $C$, denote by
$\chi(C)$ a $2$-flow of $(G,\sigma)$ with $\operatorname{{\rm
supp}}(\chi(C))=E(C)$ guaranteed by Lemma 2.2. In the following argument, all
cases only involve one $\chi(C)$ except one which involves three balanced
circuits with one common edge. Thus without loss of generality, we assume that
$\chi(C)$ is a nonnegative $2$-flow.

Take $T=T_{1}$ if $(G,\sigma)$ contains $FC_{i}$ if $i\in\\{1,2,3,9,10\\}$,
$T=T_{2}$ if $(G,\sigma)$ contains $FC_{4}$ or $FC_{11}$, and $T=T_{3}$ if
$(G,\sigma)$ contains $FC_{i}$ if $i\in\\{5,6,7,8\\}$.

Since in $FC_{1}$ or $FC_{2}$, $E(T_{1})$ is contained in two edge-disjoint
balanced circuits of length at most $4$, a contradiction to Fact A. This
proves that $(G,\sigma)$ does not contain $FC_{1}$ or $FC_{2}$.

In $FC_{3}$, any two edges in $T_{1}$ are contained in a balanced $4$-circuit,
thus by Fact A, $E_{\phi=0}=E(T_{1})$. Let $C=T_{2}\bigtriangleup T_{3}$. Then
$C$ is a balanced $4$-circuit and contains the two edges $uv_{1}$ and
$uv_{2}$. Let $\phi_{1}=\phi+\phi(v_{2}v_{3})\chi(C)$. Then $\phi_{1}$ is a
$\mathbb{Z}_{3}$-flow such that $E_{\phi_{1}=0}\subseteq E(T_{1}\bigtriangleup
T_{3})$. This contradicts Fact A since $T_{1}\bigtriangleup T_{3}$ is a
balanced $4$-circuit. This proves that $(G,\sigma)$ does not contain $FC_{3}$.

Similarly, in $FC_{4}$, by Fact A, $E_{\phi=0}=E(T_{2})$. Let
$C=T_{2}\bigtriangleup T_{3}$ which is a balanced $4$-circuit and let
$\phi_{1}=\phi+\phi(v_{4}v_{5})\chi(C)$. Then $\phi_{1}$ is a
$\mathbb{Z}_{3}$-flow such that
$E_{\phi_{1}=0}\subseteq\\{v_{3}v_{4},v_{3}v_{5}\\}\subseteq
E(T_{3}\bigtriangleup T_{4})$. This contradicts Fact A since
$T_{3}\bigtriangleup T_{4}$ is a balanced $4$-circuit. This proves that
$(G,\sigma)$ does not contain $FC_{4}$.

Suppose that $G$ contains $FC_{i}$ for some $i=5,6,7,8$. By Fact A,
$\phi(v_{4}v_{5})=0$ in $FC_{5}$ and in $FC_{i}$ where $i=6,7,8$,
$\phi(v_{3}v_{5})=0$. Let $C=T_{2}\bigtriangleup T_{3}$, which is a balanced
$4$-circuit. Let $\phi_{1}=\phi+\phi(v_{2}v_{3})\chi(C)$. Then $\phi_{1}$ is a
$\mathbb{Z}_{3}$-flow such that $E_{\phi_{1}=0}\subseteq E(T_{1}\bigtriangleup
T_{2})\cup E(T_{4})$ when $i=5,6$ and $E_{\phi_{1}=0}\subseteq
E(T_{1}\bigtriangleup T_{2})\cup E(T_{4}\bigtriangleup T_{5})$ when $i=7,8$.
In the former case, $T_{1}\bigtriangleup T_{2}$ is a balanced $4$-circuit and
$T_{4}$ is a balanced $3$-circuit and they are edg-disjoint. In the latter
case, $T_{1}\bigtriangleup T_{2}$ and $T_{4}\bigtriangleup T_{5}$ are edge-
disjoint balanced $4$-circuits. This contradicts Fact A and thus proves that
$(G,\sigma)$ does not contain $FC_{i}$ for each $i=5,6,7,8$.

Now we consider the case when $(G,\sigma)$ contains $FC_{9}$. Similar to the
above argument, we have $\phi(v_{1}v_{3})=\phi(v_{2}v_{3})=0$.

If $\phi(v_{1}v_{2})=0$, let $\phi_{1}=\phi+\phi(v_{3}v_{5})\chi(C)$ where
$C=T_{1}\bigtriangleup T_{4}$ is a balanced $4$-circuit. Then $\phi_{1}$ is a
$\mathbb{Z}_{3}$-flow such that $E_{\phi_{1}=0}\subseteq E(T_{3}\bigtriangleup
T_{4})$. This contradicts Fact A since $T_{3}\bigtriangleup T_{4}$ is a
balanced $4$-circuit.

Now we further assume $\phi(v_{1}v_{2})=\alpha\not=0$. Note that $C=T_{1}\cup
T_{3}$ is a short barbell. If one of $\phi(v_{3}v_{4})$ and $\phi(v_{3}v_{5})$
is not equal to $-\alpha$, without loss of generality, assume
$\phi(v_{3}v_{4})\not=-\alpha$. Let $\phi_{1}=\phi+\alpha\chi(C)$. Then
$\phi_{1}$ is a $\mathbb{Z}_{3}$-flow such that
$E_{\phi_{1}=0}\subseteq\\{v_{3}v_{5},v_{5}v_{4}\\}\subseteq
E(T_{2}\bigtriangleup T_{3})$. This contradicts Fact A since
$T_{2}\bigtriangleup T_{3}$ is a balanced $4$-circuit. If
$\phi(v_{3}v_{4})=\phi(v_{3}v_{5})=-\alpha$, let
$\phi_{1}=\phi-\alpha\chi(C)$. Then $\phi_{1}$ is a $\mathbb{Z}_{3}$-flow such
that $E_{\phi_{1}=0}\subseteq\\{v_{1}v_{2},v_{5}v_{4}\\}$, a contradiction to
Fact A again since $v_{1}v_{2}$ and $v_{5}v_{4}$ are contained in the balanced
$4$-circuit $v_{1}v_{2}v_{4}v_{5}v_{1}$. This proves that $(G,\sigma)$ does
not contain $FC_{9}$.

Suppose that $(G,\sigma)$ contains $FC_{10}$. Similarly as before we have that
$\phi(v_{1}v_{3})=0$ and at least one of $\phi(v_{2}v_{1})$ and
$\phi(v_{2}v_{3})$ is $0$. Let $\phi_{1}=\phi+\phi(v_{4}v_{5})\chi(C)$ where
$C=T_{1}\cup T_{3}$ is a short barbell. Then $\phi_{1}$ is a
$\mathbb{Z}_{3}$-flow such that $E_{\phi_{1}=0}\subseteq E(T_{1}\bigtriangleup
T_{4})\cup E(T_{2})$. Since $T_{1}\bigtriangleup T_{4}$ is a balanced
$4$-circuit, $T_{2}$ is a balanced triangle, and they share one common edge,
by Lemma 3.13, $(G,\sigma)$ admits a $4$-NZF, a contradiction. Thus
$(G,\sigma)$ does not contain $FC_{10}$.

Finally suppose that $(G,\sigma)$ contains $FC_{11}$. Denote
$C_{1}=T_{1}\bigtriangleup T_{2}$, $C_{2}=T_{2}\bigtriangleup T_{3}$, and
$C_{3}=T_{4}$. Note that $C_{1},C_{2},C_{3}$ are all balanced circuits sharing
a common edge $v_{2}v_{4}$.

######  Claim 5.0.1.

There is a $3$-flow $f$ such that $v_{2}v_{4}\in E_{f=0}\subseteq E(C_{1})\cup
E(C_{2})$ and $|E_{f=0}\cap E(C_{i})|\geq 2$ for each $i=1,2$.

###### Proof.

With a similar argument as before, we have
$\phi(v_{2}v_{3})=\phi(v_{3}v_{4})=0$. If $\phi(v_{2}v_{4})=0$, then by Lemma
3.8, let $f$ be a $3$-flow with $\operatorname{{\rm
supp}}(f)=\operatorname{{\rm supp}}(\phi)$ which is a desired $3$-flow.

Assume $\phi(v_{2}v_{4})=a\not=0$. If $\phi(v_{1}v_{2})=\phi(v_{1}v_{3})=b$,
let $\phi_{1}=\phi+b\chi(C_{1})$. Then
$E_{\phi_{1}=0}=\\{v_{2}v_{3},v_{2}v_{4}\\}\subseteq E(C_{1})$, a
contradiction to Fact A. Thus $\phi(v_{1}v_{2})\not=\phi(v_{1}v_{3})$. Then
$a\in\\{\phi(v_{1}v_{2}),\phi(v_{1}v_{3})\\}$. Let
$\phi_{2}=\phi-a\chi(C_{1})$. Then $v_{2}v_{4}\in E_{\phi_{2}=0}$ and
$|E_{\phi_{2}=0}\cap E(C_{i})|=2$ for each $i=1,2$. By Lemma 3.8, let $g$ be
the corresponding $3$-flow of $\phi_{2}$ with $\operatorname{{\rm
supp}}(g)=\operatorname{{\rm supp}}(\phi_{2})$ which is a desired $3$-flow.
This prove the claim. ∎

Let $f$ be a $3$-flow described in Claim 5.0.1. Note $|\\{\pm 1,\pm
2\\}\setminus f(C_{i})|\geq 2$ for each $i=1,2$.

If $\\{1,-1\\}\setminus f(C_{i})\not=\emptyset$, take
$\alpha_{i}\in\\{1,-1\\}\setminus f(C_{i})$. Otherwise $f(C_{i})=\\{0,1,-1\\}$
and take $\alpha_{i}\in\\{2,-2\\}$. In the case when both
$|\alpha_{1}|=|\alpha_{2}|=2$, we choose $\alpha_{1}=2$ and $\alpha_{2}=-2$.
Then $g=f+\alpha_{1}\chi(C_{1})+\alpha_{2}\chi(C_{2})$ is a $4$-flow such that
$E_{g=\pm 3}\subseteq E(C_{1})\cup E(C_{2})$ and
$E_{g=0}\subseteq\\{v_{2}v_{4}\\}$. Since $(G,\sigma)$ does not admit a
$4$-NZF, $g(v_{2}v_{4})=0$. Since $T_{4}$ is a balanced triangle and
$|g(e)|\leq 2$ for each $e\in E(T_{4})$, one can extend $g$ to be a $4$-NZF of
$(G,\sigma)$, a contradiction. This proves that $(G,\sigma)$ does not contain
$FC_{11}$ and thus completes the proof of (III). $\Box$

$u$$v$$w_{1}$$w_{2}$$w_{3}$$T_{1}$$T_{2}$$T_{3}$$FC_{1}$

$u$$v$$w_{1}$$w_{2}$$w_{3}$$x$$T_{1}$$T_{2}$$FC_{2}$

$v_{1}$$v_{2}$$v_{3}$$u$$T_{3}$$T_{1}$$T_{2}$$FC_{3}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$T_{1}$$T_{2}$$T_{3}$$T_{4}$$FC_{4}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$T_{1}$$T_{2}$$T_{3}$$T_{4}$$FC_{5}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$T_{1}$$T_{2}$$T_{3}$$T_{4}$$FC_{6}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$T_{1}$$T_{2}$$T_{3}$$T_{4}$$T_{5}$$FC_{7}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$T_{1}$$T_{2}$$T_{3}$$T_{4}$$T_{5}$$FC_{8}$

$v_{3}$$v_{1}$$v_{2}$$v_{4}$$v_{5}$$T_{4}$$T_{1}$$T_{2}$$T_{3}$$FC_{9}$

$v_{3}$$v_{1}$$v_{2}$$v_{4}$$v_{5}$$T_{4}$$T_{1}$$T_{2}$$T_{3}$$FC_{10}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$T_{4}$$T_{1}$$T_{2}$$T_{3}$$FC_{11}$

Figure 4: Forbidden configurations: the dotted lines are negative edges.

(IV) There is no triangle-path $T_{1}T_{2}\cdots T_{m}$ in $(G,\sigma)$ such
that $m\geq 3$, $T_{1}$ and $T_{m}$ are unbalanced, and $T_{i}$ is balanced
for each $i\in\\{2,\dots,m-1\\}$.

Proof of (IV). Suppose to the contrary that there is a triangle-path
$H=T_{1}T_{2}\cdots T_{m}$ such that $m\geq 3$, $T_{1}$ and $T_{m}$ are
unbalanced and $T_{i}$ is balanced for each $i=\\{2,\dots,m-1\\}$. Denote by
$H^{\prime}=T_{2}\cdots T_{m-1}$. Denote $E(T_{1})=\\{e_{1},e_{2},e_{3}\\}$
and $E(T_{m})=\\{e_{4},e_{5},e_{6}\\}$ where $e_{3}\in E(T_{1})\cap E(T_{2})$
and $e_{6}\in E(T_{m})\cap E(T_{m-1})$. Let $x$ be the common endvertex of
$e_{1}$ and $e_{2}$ and $y$ be the common endvertex of $e_{4}$ and $e_{5}$.
Let $C=T_{1}\bigtriangleup T_{2}\bigtriangleup\cdots\bigtriangleup T_{m}$.
Then $C$ is a balanced circuit containing $e_{i}$ for each $i=1,2,4,5$.

Take $T=T_{1}$. Then $E_{\phi=0}\subseteq E(T_{1})$. Since $e_{3}$ belongs to
the balanced triangle $T_{2}$, by Lemma 3.11, either $\phi(e_{1})=0$ or
$\phi(e_{2})=0$.

If $d(x)\geq 3$, there is a triangle $T_{0}$ such that $T_{0}$ and $T_{1}$
share exactly one of $e_{1}$ and $e_{2}$ since by (II), $G$ is locally
connected. Let $C_{1}=T_{0}$ if $T_{0}$ is balanced otherwise let
$C_{1}=T_{0}\bigtriangleup T_{1}$ which is a balanced $4$-circuit. Without
loss of generality assume $e_{1}\in E(C_{1})$.

Similarly if $d(y)\geq 3$, there is a triangle $T_{m+1}$ such that $T_{m+1}$
and $T_{m}$ share exactly one of $e_{4}$ and $e_{5}$. Let $C_{2}=T_{m+1}$ if
$T_{m+1}$ is balanced otherwise let $C_{2}=T_{m+1}\bigtriangleup T_{m}$ which
is a balanced $4$-circuit. Without loss of generality assume $e_{4}\in
E(C_{2})$.

Let $\alpha=\phi(e_{5})$ and $\phi_{1}=\phi+\alpha\chi(C)$.

We first show $\phi(e_{1})\not=\phi(e_{2})$. Suppose the contradiction that
$\phi(e_{1})=\phi(e_{2})$. Then $\phi(e_{1})=\phi(e_{2})=0$ and thus
$E_{\phi_{1}=0}\subseteq E(H^{\prime})\cup\\{e_{4}\\}$.

If $\phi_{1}(e_{4})\not=0$, then $E_{\phi_{1}=0}\subseteq E(H^{\prime})$. By
Lemma 3.12, there is a $Z_{3}$-flow $\phi_{2}$ such that
$E_{\phi_{2}=0}\subseteq\\{e_{6}\\}$, a contradiction to Fact A.

If $\phi_{1}(e_{4})=0$, then $\phi(e_{4})\not=\phi(e_{5})$. This implies
$d(y)\geq 3$ and thus $C_{2}$ exists. If $E(C_{2})\cap
E(H^{\prime})\not=\emptyset$, let $e_{0}\in E(C_{2})\cap E(H^{\prime})$.
Otherwise, let $e_{0}=e_{6}$. By Lemma 3.12, there is a $Z_{3}$-flow
$\phi_{3}$ such that $E_{\phi_{3}=0}\subseteq\\{e_{0},e_{4}\\}\subseteq
E(C_{2})$, a contradiction to Fact A since $C_{2}$ is a balanced circuit of
length at most $4$. This shows that $\phi(e_{1})\not=\phi(e_{2})$, which
implies $d(x)\geq 3$. By symmetry, we also have $d(y)\geq 3$. Therefore both
$C_{1}$ and $C_{2}$ exist.

Since $e_{1}\in E(C_{1})$ and $e_{3}\in E(T_{2})$, we have $\phi(e_{2})=0$.
Then $E_{\phi_{1}=0}\subseteq E(H^{\prime})\cup\\{e_{1},e_{4}\\}$. If
$(E(C_{1})\cup E(C_{2}))\cap E(H^{\prime})\not=\emptyset$, let $e_{7}$ be an
edge in $(E(C_{1})\cup E(C_{2}))\cap E(H^{\prime})$. Otherwise let
$e_{7}=e_{3}$. By Lemma 3.12, one can obtained a $Z_{3}$-flow $\phi_{4}$ from
$\phi_{1}$ such that $E_{\phi_{4}=0}\subseteq\\{e_{1},e_{4},e_{7}\\}$. Note
that if $C_{i}$ is a circuit of length $4$ for some $i=1,2$, then $e_{7}\in
E(C_{i})\cap E(H^{\prime})$.

If $C_{1}$ and $C_{2}$ are edge-disjoint, then we have either
$\\{e_{1},e_{4},e_{7}\\}\subseteq E(C_{1})\cup E(C_{2})$ or
$\\{e_{1},e_{4},e_{7}\\}\subseteq E(C_{1})\cup E(C_{2})\cup E(T_{2})$ where
$C_{1},C_{2},T_{2}$ are edge-disjoint balanced triangles. The former case
contradicts Fact A. In the latter case, by Lemma 3.8, there is an integer
$3$-flow flow $f$ such that $\operatorname{{\rm supp}}(f)=\operatorname{{\rm
supp}}(\phi_{4})$. By Lemma 3.9 (considering $f$ as an integer $4$-flow), $f$
can be extended to a $4$-NZF of $G$, a contradiction. Therefore $C_{1}$ and
$C_{2}$ are not edge-disjoint.

If $C_{1}$ is a triangle, then by Lemma 3.12, one can obtain a $Z_{3}$-flow
$\phi_{5}$ from $\phi_{4}$ such that $|E_{\phi_{5}=0}|\leq 4$ and
$E_{\phi_{5}=0}\subseteq E(C_{2})\cup\\{e_{7}\\}$ since $C_{1}$ and $C_{2}$
are not edge-disjoint. Since $e_{7}$ is contained in a balanced triangle and
$C_{2}$ is a balanced $4$-circuit, by Lemma 3.11 or Lemma 3.13, $(G,\sigma)$
has a $4$-NZF, a contradiction. Thus $C_{1}$ is a $4$-circuit. By symmetry,
$C_{2}$ is also a $4$-circuit. This implies $e_{3}\in E(C_{1})$ and $e_{6}\in
E(C_{2})$ and $\\{e_{1},e_{4}\\}\subseteq
E_{\phi_{4}=0}\subseteq\\{e_{1},e_{4},e_{7}\\}\subseteq E(C_{1})\cup
E(C_{2})$.

Since $C_{1}$ and $C_{2}$ are not edge-disjoint, there is a
$\beta\in\mathbb{Z}_{3}$ such that $\phi_{6}=\phi_{4}+\beta\chi(C_{1})$
satisfying $E_{\phi_{6}=0}\subseteq E(C_{2})\cup\\{e_{3}\\}$. Since
$\\{e_{3},e_{7}\\}\subseteq E(H^{\prime})$, by Lemma 3.12, one can obtain a
$Z_{3}$-flow $\phi_{7}$ from $\phi_{6}$ such that $E_{\phi_{7}=0}\subseteq
E(C_{2})$, a contradiction to Fact A. This completes the proof of (IV).

(V) For any triangle-path $H=T_{1}T_{2}T_{3}$ with each $T_{i}$ unbalanced,
$H$ is an induced subgraph of $(G,\sigma)$.

Proof of (V). Suppose to the contrary that $H$ is not induced. Denote
$V(H)=\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\}$ where
$V(T_{i})=\\{v_{i},v_{i+1},v_{i+2}\\}$ for each $i=1,2,3$.

Since by (III), $(G,\sigma)$ does not contain $FC_{9}$ or $FC_{10}$, $v_{1}$
and $v_{5}$ are not adjacent. Then either $v_{1}$ and $v_{4}$ are adjacent or
$v_{2}$ and $v_{5}$ are adjacent. Without loss of generality, assume $v_{1}$
and $v_{4}$ are adjacent. Denote $T_{4}=v_{1}v_{3}v_{4}$. Since by (III)
$(G,\sigma)$ does not contain $FC_{3}$, $T_{4}$ is balanced. Then
$T_{2},T_{3}$ and $T_{4}$ form a $FC_{1}$, a contradiction to (III) again.
This completes the proof of (V).

$\Gamma_{1}$

$\Gamma_{2}$

$\Gamma_{3}$

Figure 5: Three graphs formed by four unbalanced triangles

The final step. By (III), $(G,\sigma)$ does not contain any graph of Figure 4
as a subgraph. We can further assume that $(G,\sigma)$ contains two edge-
disjoint unbalanced triangles by (I).

By (IV), let $H=T_{1}T_{2}\ldots T_{m}$ be a triangle-path such that each
triangle $T_{i}$ is unbalanced and $E(T_{1})\cap E(T_{m})=\emptyset$. We
choose $H$ such that $m$ is as large as possible. Since $(G,\sigma)$ contains
two edge-disjoint unbalanced triangles by (I) and does not contain $FC_{8}$ by
(III), we have $3\leq m\leq 4$. One can easily see that $H$ admits a $4$-NZF.
Since $(G,\sigma)$ does not admit a $4$-NZF, $H\not=G$. Since $G$ is
triangularly connected, there must be a triangle $T_{5}\not=T_{i}$ for each
$i=1,2,3$ such that $E(T_{5})\cap E(H)\not=\emptyset$.

If $m=4$, then $H=\Gamma_{1}$ or $\Gamma_{3}$ in Figure 5. If $m=3$, by (V),
$H$ is an induced subgraph and hence $|E(T_{4})\cap E(H)|=1$. Since by (III),
$G$ does not contain $FC_{i}$ for each $i=1,2,5,6,11$, $H$ must be one of
$\Gamma_{i}$ in Figure 5. It is easy to see that each $\Gamma_{i}$ admits a
$4$-NZF and thus $(G,\sigma)\not=\Gamma_{i}$ for each $i$. Since $G$ is
triangularly connected, there is a triangle $T_{6}$ such that
$T_{6}\not=T_{i}$ for each $i=1,2,3,4$ and $E(T_{6})\cap E(H)\not=\emptyset$.
By the maximality of $m$ and since $(G,\sigma)$ does not contain $FC_{i}$ for
each $i=1,2,4,5,6,11$, we have $|E(T_{6})\cap E(H)|\geq 2$. By (V),
$H=\Gamma_{3}$ and thus by (IV) $G=(W_{5},\sigma^{*})$, a contradiction. This
completes the proof of the theorem. $\Box$

## References

  * [1] J. A. Bondy, U.S.R. Murty, Graph Theory, Springer, New York, 2008.
  * [2] A. Bouchet, Nowhere-zero integral flows on bidirected graph, J. Combin. Theory Ser. B 34 (1983) 279–292.
  * [3] R. Diestel, Graph Theory, Fourth edn. Springer-Verlag (2010).
  * [4] J. Cheng, Y. Lu, R. Luo and C.-Q. Zhang, Signed graphs: from modulo flows to integer-valued flows, SIAM J. Discrete Math. 32 (2018) 956-965.
  * [5] M. DeVos, J. Li, Y. Lu, R. Luo, C.-Q. Zhang, Z. Zhang, Flows on flow-admissible signed graphs, J. Combin. Theory Ser. B 149 (2021) 198-221.
  * [6] G. Fan, H.-J. Lai, R. Xu, C.-Q. Zhang, C. Zhou, Nowhere-zero 3-flows in triangularly connected graphs, J. Combin. Theory Ser. B 98 (2008) 1325-1336.
  * [7] L. Hu, X. Li, Nowhere-zero flows on signed wheels and signed fans, Bull. Mayays. Sci. Soc. 41 (2018) 1697-1709.
  * [8] W. Imrich, I. Peterin, S. Špacapan and C.-Q. Zhang, NZ-flows in strong products of graphs, J. Graph Theory 64 (2010) 267-276.
  * [9] H.J. Lai, Nowhere-zero $3$-flows in locally connected graphs, J. Graph Theory 42 (2003) 211-219.
  * [10] Y. Lu, R. Luo, M. Schubert, E. Steffen, and C.-Q Zhang, Flows on signed graphs without long barbells, SIAM J. Discrete Math. 34 (2020) 2166-2182.
  * [11] Y. Lu, R. Luo, C.-Q. Zhang, Multiple weak 2-linkage and its applications on integer flows of signed graphs, European J. Combin. 69 (2018) 36-48.
  * [12] Y. Lu, R. Luo, C.-Q. Zhang, Z. Zhang, Signed graphs, nonorientable surfaces, and integer flows, preprint.
  * [13] T. Kaiser and E. Rollová, Nowhere-zero flows in signed series-parallel graphs, SIAM J. Discrete Math. 30 (2016) 1248-1258.
  * [14] E. Máčajová and E. Rollová, Nowhere-zero flows on signed complete and complete bipartite graphs, J. Graph Theory 78 (2015) 809-815.
  * [15] E. Mačajova and M Škoviera, Nowhere-zero flows on signed eulerian graphs, SIAM J. Discrete Math. 31 (2017) 1937-1952.
  * [16] A. Raspaud and X. Zhu, Circular flow on signed graphs, J. Combin. Theory Ser. B 101 (2011) 464-479.
  * [17] M. Schubert and E. Steffen, Nowhere-zero flows on signed regular graphs, European J. Combin. 48 (2015) 34-47.
  * [18] W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80-91.
  * [19] W. T. Tutte, On the imbedding of linear graphs in surfaces, Proc. London Math. Soc. Ser. 2 51 (1949) 474-483.
  * [20] X. Wang, Y. Lu, C.-Q Zhang, S. Zhang, Six flows on almost balanced signed graphs, J. Graph Theory 92 (2019) 394-404.
  * [21] D. B. West, Introduction to Graph Theory, Upper Saddle River, NJ: Prentice Hall, (1996).
  * [22] Y. Wu, D. Ye, W. Zang and C.-Q. Zhang, Nowhere-zero $3$-flows in signed graphs, SIAM J. Discrete Math. 28 (3) (2014) 1628-1637.
  * [23] R. Xu, C.-Q. Zhang, On flows in bidirected graphs, Discrete Math. 299 (2005) 335–343.
  * [24] O. Zýka, Nowhere-zero 30-flow on bidirected graphs, Thesis, Charles University, Praha, KAM-DIMATIA Series 87-26, 1987.