# Planar Graphs with Homomorphisms to the 9-cycle

Daniel W. Cranston, Jiaao Li, Zhouningxin Wang, and Chunyan Wei Virginia
Commonwealth University, Dept. of Computer Science; Richmond, VA, USA;
<EMAIL_ADDRESS>of Mathematical Sciences and LPMC, Nankai University,
Tianjin 300071, China<EMAIL_ADDRESS>of Mathematical Sciences
and LPMC, Nankai University, Tianjin 300071, China;
<EMAIL_ADDRESS>for Combinatorics and LPMC, Nankai University,
Tianjin 300071, China<EMAIL_ADDRESS>
###### Abstract

We study the problem of finding homomorphisms into odd cycles from planar
graphs with high odd-girth. The Jaeger-Zhang conjecture states that every
planar graph of odd-girth at least $4k+1$ admits a homomorphism to the odd
cycle $C_{2k+1}$. The $k=1$ case is the well-known Grötzsch’s $3$-coloring
theorem. For general $k$, in 2013 Lovász, Thomassen, Wu, and Zhang showed that
it suffices to have odd-girth at least $6k+1$. Improvements are known for
$C_{5}$ and $C_{7}$ in [Combinatorica 2017, SIDMA 2020, Combinatorica 2022].
For $C_{9}$ we improve this hypothesis by showing that it suffices to have
odd-girth 23. Our main tool is a variation on the potential method applied to
modular orientations. This allows more flexibility when seeking reducible
configurations. The same techniques also prove some results on circular
coloring of signed planar graphs.

Keywords. homomorphism, modular orientation, potential method.

##  1 Introduction

###  1.1 Homomorphisms to odd cycles

A _homomorphism_ (or _map_) of a graph $G$ to another graph $H$ is a function
$\varphi:V(G)\to V(H)$ that preserves adjacency. Note that a graph $G$ is
$k$-colorable if and only if $G$ has a homomorphism to $K_{k}$. So the study
of graph homomorphisms extends and strengthens many results on graph coloring.
Grötzsch’s $3$-coloring theorem famously states that every planar graph of
odd-girth at least $5$ admits a homomorphism to $C_{3}$. Recall that the _odd-
girth_ of a graph is the length of its shortest odd cycle. The following
conjecture, which generalizes Grötzsch’s theorem, concerns homomorphisms of a
graph $G$ to odd cycles when $G$ is planar with large odd-girth. (It is worth
noting that $C_{2k+3}$ maps to $C_{2k+1}$ for all $k\geqslant 1$, but not vice
versa. So proving that a graph $G$ maps to $C_{2k+3}$ is stronger than proving
that $G$ maps to $C_{2k+1}$.)

######  Conjecture 1.1.

Every planar graph of odd-girth at least $4k+1$ admits a homomorphism to
$C_{2k+1}$.

If true, 1.1 is best possible. To see this, begin with a cycle $C_{4k-1}$; add
a new vertex $v$ and vertex-disjoint paths from $v$ to all vertices of the
cycle, with each path of length $2k-1$. The resulting graph is planar with
odd-girth $4k-1$, but it is straightforward to check111Observe that in a
hypothetical homomorphism to $C_{2k+1}$ no vertex on the original cycle
$C_{4k-1}$ has the same image as $v$; thus, this $C_{4k-1}$ must map into a
path, which is impossible. that this graph has no homomorphism to $C_{2k+1}$.

For planar graphs, 1.1 is the dual version of Jaeger’s 1982 Circular Flow
Conjecture [7], which asserts that every $4k$-edge-connected multigraph admits
a circular $\frac{2k+1}{k}$-flow. A _circular $\frac{p}{q}$-flow_, given
positive integers $p$ and $q$ with $p\geqslant 2q$, of a graph $G$ is a flow
$(D,f)$ such that $q\leqslant|f(e)|\leqslant p-q$ for every edge $e\in E(G)$.
So a circular $\frac{2k+1}{k}$-flow requires that $|f(e)|\in\\{k,k+1\\}$ for
all $e$. In 2018, Jaeger’s conjecture was disproved [5] for all $k\geqslant
3$. However, the known counterexamples are all non-planar; so it is still
possible that 1.1 is true. This problem remains open.

Let $G$ be a planar graph with girth $g$. In 1996, Nešetřil and Zhu [14]
proved that $G$ maps to $C_{2k+1}$ whenever $g\geqslant 10k-4$. In 2001, Zhu
[17] improved this hypothesis to $g\geqslant 8k-3$. And in 2004, Borodin, Kim,
Kostochka, and West [1] further improved this hypothesis to
$g\geqslant\frac{20k-2}{3}$. Finally, in 2013, Lovász, Thomassen, Wu, and
Zhang [12] proved that $G$ maps to $C_{2k+1}$ if $G$ has odd-girth at least
$6k+1$.

The general result [12] for odd-girth at least $6k+1$ has been improved for
small $k$. Let $g_{o}$ denote the odd-girth of $G$. When $k=2$, [12] implies
that $G$ maps to $C_{5}$ when $g_{o}\geqslant 13$. Dvořák and Postle [3] and
Cranston and Li [2] improved this to $g_{o}\geqslant 11$. When $k=3$, [12]
implies that $G$ maps to $C_{7}$ when $g_{o}\geqslant 19$. Cranston and Li [2]
and Postle and Smith-Roberge [15] both improved this to $g_{o}\geqslant 17$.
Continuing with this line of study, when $k=4$ we improve the hypothesis of
[12] from $g_{o}\geqslant 25$ to $g_{o}\geqslant 23$. That is, we prove the
following.

######  Theorem 1.2.

Every planar graph of odd-girth at least $23$ admits a homomorphism to
$C_{9}$.

Recall that 1.1 posits that the hypothesis $g_{o}\geqslant 23$ in this result
can be improved to $g_{o}\geqslant 17$, which if true would be best possible.

###  1.2 Modular orientations

For a plane graph $G$ and its planar dual $G^{*}$, the dual of each cycle $C$
in $G$ is a minimal edge cut $C^{*}$ in $G^{*}$. So $G^{*}$ has odd-girth at
least 23 if and only if in $G$ every minimal edge cut of odd size has size at
least 23. Such a graph $G$ has _odd-edge-connectivity_ at least 23. We find it
more convenient to prove Theorem 1.2 in its dual formulation. But before
stating this version we need a new definition, proposition, and lemma. The
proposition is an easy exercise222Given a map $\varphi$ from $G$ to
$C_{2k+1}$, the faces $f$ of $G^{*}$ take colors $\varphi^{*}(f)$ from the
corresponding vertices of $G$. Now each edge $e$ of $G^{*}$, with face $f_{1}$
on the left and face $f_{2}$ on the right, has flow value
$k(\varphi^{*}(f_{1})-\varphi^{*}(f_{2}))$. It is straightforward to check
that this process yields a circular $\frac{2k+1}{k}$-flow of $G^{*}$., and the
lemma was proved by Jaeger [6] in 1984.

######  Definition 1.3.

Given an orientation $D$ of $G$, if the outdegree of $v$ is congruent to the
indegree of $v$ modulo $2k+1$ (i.e., $d^{+}_{D}(v)-d^{-}_{D}(v)\equiv
0\pmod{2k+1}$) for every vertex $v\in V(G)$, then we call $D$ a _modular
$(2k+1)$-orientation_.

######  Proposition 1.4.

A plane graph $G$ admits a homomorphism to $C_{2k+1}$ if and only if its
planar dual $G^{*}$ admits a circular $\frac{2k+1}{k}$-flow.

######  Lemma 1.5.

[6] A graph $G$ has a circular $\frac{2k+1}{k}$-flow if and only if $G$ admits
a modular $(2k+1)$-orientation.

Suppose that $G^{*}$ is a plane graph with odd-girth at least $23$. Now $G$
has odd-edge-connectivity at least $23$. By Proposition 1.4, $G^{*}$ admits a
homomorphism to $C_{9}$ if and only if $G$ admits a circular
$\frac{9}{4}$-flow. And by Lemma 1.5, this is equivalent to $G$ having a
modular $9$-orientation. Thus, we reach the following dual formulation of
Theorem 1.2, which is what we will prove.

Theorem 1.2′. Every planar graph with odd-edge-connectivity at least $23$
admits a modular 9-orientation.

In fact, we will consider a more general type of orientation, which includes
modular $k$-orientations as a special case. But we defer this definition until
Section 2.1. In the remainder of this section, we present much of the
intuition behind our proofs.

When proving graph coloring results, it is typical to phrase hypotheses in
terms of _maximum average degree_ , which is the maximum of the average
degrees of all subgraphs. Given a bound on maximum average degree, we can find
some reducible configurations with good properties. For instance, given a
graph $G$, we form a smaller graph $G^{\prime}$ by deleting a suitable
subgraph $H$, we color $G^{\prime}$ by induction, and we can then extend every
proper coloring of $G^{\prime}$ to $G$. To prove Theorem 1.2′, we will
construct a modular 9-orientation. Thus we seek a concept, in the context of
modular orientations, that parallels reducible configurations for graph
coloring.

The dual of edge deletion in a planar graph $G$ is edge _contraction_ in its
planar dual $G^{*}$. For an edge $e\in E(G)$, _contracting_ $e$ means
identifying its two endpoints and deleting the resulting loop. We denote the
resulting graph by $G/e$. Now the graph $G/H$, where $H\subseteq G$, is formed
from $G$ by contracting all edges of $E(H)$. Thus, our reducible
configurations in this context will be subgraphs $H$ such that we can form
$G^{\prime}$ by contracting $H$, find a modular orientation for $G^{\prime}$,
and then extend this orientation to a modular orientation for $G$.
Intuitively, such a process is easier when $G$ has higher edge-connectivity.
But rather than working directly with edge-connectivity, we rely on a weight
function introduced in [2]. Analogous to maximum average degree, the weight of
a graph is defined as a minimum over all vertex-partitions of the number of
edges between parts, minus a term linear in the number of parts. Intuitively,
a graph with higher edge-connectivity has higher weight. This weight function
is motivated by the Nash-Williams–Tutte Theorem [13, 16], which characterizes
graphs with $k$ edge-disjoint spanning trees, for each positive integer $k$.

######  Definition 1.6.

For a graph $G$ and a partition $\mathcal{P}$ of $V(G)$ with parts
$P_{1},P_{2},\ldots,P_{t}$, the _weight function_ is defined as follows:

$w_{G}(\mathcal{P}):=\sum_{i=1}^{t}d(P_{i})-23t+42.$ (1)

Here $d(P_{i})$ is the number of the edges of $E(G)$ with exactly one endpoint
in $P_{i}$.

The _weight_ of a graph $G$ is the minimum weight over all its partitions,
i.e., $w(G):=\min\limits_{\mathcal{P}}w_{G}(\mathcal{P})$.

We will prove our main results for all planar graphs $G$ with $w(G)\geqslant
0$, excluding a few well-understood exceptional graphs. To help build
intuition, first consider the trivial partition $\mathcal{P}_{0}$, where each
vertex forms its own part. Here the inequality $0\leqslant w(G)\leqslant
w_{G}(\mathcal{P}_{0})=2e(G)-23v(G)+42$ implies that
$e(G)\geqslant\frac{1}{2}(23v(G)-42)$. It is helpful to observe that
$w(G/H)\geqslant w(G)$ for all graphs $G$ and connected subgraphs $H$. Thus,
we aim to find a “good” subgraph $H$, recursively find the desired orientation
for $G/H$, and then extend this orientation to $G$, due to our choice of $H$.
However, this is not always possible. Sometimes a contractible graph $H$ is
not a subgraph of $G$, but $G$ contains some $H^{\prime}$ formed from $H$ by
deleting a few edges. In this case, we can often “lift” pairs of edges outside
$E(H^{\prime})$ to simulate the missing edges of $H$.

It turns out that this process of finding good reductions, via contraction
(and sometimes lifting)—which is the key to proving Theorem 1.2′—also yields a
result on $r$-flows in _signed_ planar graphs (see Theorem 1.12). Thus, we
extract from the proof of Theorem 1.2′ a key structural result, Theorem 1.11
(see below), the proof of which requires most of our work.

It is good now to explain the choice of the constants $23$ and $42$ in the
definition of the weight function. The number $23$ in the weight function
comes from our desired edge-connectivity. Given a $23$-edge-connected graph
$G$, clearly $w(G)\geqslant 42$, since for every partition
$\\{P_{1},P_{2},\ldots,P_{t}\\}$ of $V(G)$, each term $d(P_{i})$ in the sum is
at least $23$; thus, our results will apply. We will prove our main theorem by
induction, and it is convenient for the inductive hypothesis to be satisfied
by certain graphs of small order that are not 23-edge-connected. This
motivates introducing the additive constant 42, which ensures333We have some
flexibility in picking this constant $c$. We need $c\geqslant 42$ to ensure
that $w(G)\geqslant 0$ for every 4-vertex graph with at least 25 edges; see
Lemma 2.2(i). And we need $c\leqslant 45$ to get a contradiction via
discharging in Section 4.2; see Equation 3. Proving Theorem 1.11 with a larger
value of $c$ would be a stronger result. However, proving such a statement
would likely require much more work, since the analogous set
$\mathcal{N}\cup\mathcal{W}^{*}$ of exceptional graphs would be larger. We
prefer to keep the proof as simple as possible, which is why we chose $c=42$.
that we will have $w(G)\geqslant 0$ for these various graphs of small order.

$\alpha$$x$$y$ (a) $\alpha K_{2}$

$x$$y$$z$$a$$c$$b$ (b) $T_{a,b,c}$

$u_{1}$$u_{2}$$u_{3}$$w$$a$$c$$b$ (c) multi-$K_{4}$

Figure 1: The graphs $\alpha K_{2}$, $T_{a,b,c}$, and multi-$K_{4}$.

But this additive term also brings complications, since now our theorem’s
hypothesis will be satisfied by some small graphs that do not satisfy the
desired conclusion. Thus, we must classify exactly which small graphs do and
do not satisfy this conclusion. So we define the following two families of
graphs: $\mathcal{N}$ and $\mathcal{W}^{*}$. As shown in Figure 1, the graph
$\alpha K_{2}$ has vertex set $\\{x,y\\}$ with its vertices joined by $\alpha$
parallel edges ($\alpha\geqslant 1$), and $T_{a,b,c}$ has vertex set
$\\{x,y,z\\}$ with its pairs of vertices joined by $a$, $b$, and $c$ parallel
edges ($\min\\{a,b,c\\}\geqslant 1$).

$\displaystyle\mathcal{N}:=\\{\alpha K_{2}\colon\alpha\leqslant
7\\}\cup\\{T_{a,b,c}\colon a+b+c\leqslant 15\\}$
$\displaystyle\mathcal{W}^{*}:=\\{8K_{2}\\}\cup\\{T_{a,b,c}\colon
a+b+c=16,\delta\geqslant 9\\}$

As we will explain in more detail when we state Theorem 3.1 (see Section 3),
all graphs in $\mathcal{N}$ are too sparse to satisfy our desired conclusion,
so we will need to explicitly exclude them from our main theorem. Graphs in
$\mathcal{W}^{*}$ will satisfy our conclusion, but only barely. So we will
need to handle them more delicately than other graphs to which our main result
applies.

When specifying a graph formed by contraction, we will frequently use the
following definition. For a graph $G$ and a partition $\mathcal{P}$ with parts
$P_{1},P_{2},\ldots,P_{t}$ of $V(G)$, let $G/\mathcal{P}$ denote the graph
formed from $G$ by identifying all the vertices of $G[P_{i}]$ for each
$i\in[t]$. Let $|\mathcal{P}|$ denote the number of parts in $\mathcal{P}$ and
observe that $v(G/\mathcal{P})=|\mathcal{P}|$. We will often want to know the
weight of $\alpha K_{2}$, $T_{a,b,c}$, and graphs with four vertices, so we
record the following observation for easy reference.

######  Observation 1.7.

  1. (1)

Each graph $\alpha K_{2}$ satisfies $w(\alpha K_{2})=2\alpha-4$.

  2. (2)

Each graph $T_{a,b,c}$ without $8K_{2}$ satisfies $w(T_{a,b,c})=2(a+b+c)-27$.

  3. (3)

Each graph $G$ on four vertices without $8K_{2}$ satisfies $w(G)=2e(G)-50$.

###### Proof.

For $\alpha K_{2}$, $w(\alpha K_{2})=2\alpha-23\times 2+42=2\alpha-4$.

In the remaining two cases, every two vertices are joined by at most $7$
parallel edges, that is, we assume $\mu\leqslant 7$, where $\mu$ is the
maximum multiplicity over all edges in the graph we consider. For a graph
$T_{a,b,c}$, let $\mathcal{P}_{0}$ be its trivial partition, and let
$\mathcal{P}$ be an arbitrary partition with two parts. Since $\mu\leqslant
7$, note that $w_{\scriptscriptstyle T_{a,b,c}}(\mathcal{P})\geqslant
w_{\scriptscriptstyle T_{a,b,c}}(\mathcal{P}_{0})+23-2\times
7>w_{\scriptscriptstyle T_{a,b,c}}(\mathcal{P}_{0})$. Thus the minimum in the
definition of $w(T_{a,b,c})$ is achieved by the trivial partition (with $3$
parts). For a graph $G$ with $v(G)=4$, let $\mathcal{P}_{0}$ be the trivial
partition, let $\mathcal{P}_{1}$ be an arbitrary partition with three parts,
and $\mathcal{P}_{2}$ be an arbitrary partition with two parts. Similar to the
above discussion, we have $w_{G}(\mathcal{P}_{0})<w_{G}(\mathcal{P}_{1})$. In
fact, we also have $w_{G}(\mathcal{P}_{2})\geqslant
w_{G}(\mathcal{P}_{0})+2\times 23-2\times 3\times 7>w_{G}(\mathcal{P}_{0})$.
Hence, $w(G)=w_{G}(\mathcal{P}_{0})=2e(G)-23v(G)+42$. ∎

In particular, $w(\alpha K_{2})\leqslant 10$ when $\alpha\leqslant 7$ and
$w(8K_{2})=12$. Similarly, $w(T_{a,b,c})\leqslant 3$ when $a+b+c\leqslant 15$
and $w(T_{a,b,c})=5$ when $a+b+c=16$. Hence, all $G\in\mathcal{N}$ satisfy
$w(G)\leqslant\max\\{3,10\\}=10$ and all $G\in\mathcal{W}^{*}$ satisfy
$w(G)\leqslant\max\\{5,12\\}=12$. Now a short case analysis yields the
following observation.

######  Observation 1.8.

Given a graph $G$ and a partition $\mathcal{P}$ of $V(G)$,

  1. (1)

if $w_{G}(\mathcal{P})\geqslant 11$, then $G/\mathcal{P}\notin\mathcal{N}$;

  2. (2)

if $w_{G}(\mathcal{P})\geqslant 13$, then
$G/\mathcal{P}\notin\mathcal{N}\cup\mathcal{W}^{*}$;

  3. (3)

if $w_{G}(\mathcal{P})\geqslant 4$ and $|\mathcal{P}|\geqslant 3$, then
$G/\mathcal{P}\notin\mathcal{N}$;

  4. (4)

if $w_{G}(\mathcal{P})\geqslant 6$ and $|\mathcal{P}|\geqslant 3$, then
$G/\mathcal{P}\notin\mathcal{N}\cup\mathcal{W}^{*}$;

  5. (5)

if $w_{G}(\mathcal{P})\geqslant 6$ and $G$ is $9$-edge-connected, then
$G/\mathcal{P}\notin\mathcal{N}\cup\mathcal{W}^{*}$.

When proving our main structural theorem by induction, it is helpful to know
that no sequence of edge contractions yields a graph in $\mathcal{N}$; that
is, for all partitions $\mathcal{P}$, we have
$G/\mathcal{P}\notin\mathcal{N}$. This motivates the following two closely
related definitions.

######  Definition 1.9.

Let $G$ be a connected graph such that $v(G)\geqslant 2$.

  1. (i)

If $w(G)\geqslant 0$, $G\notin\mathcal{N}$, and
$G/\mathcal{Q}\notin\mathcal{N}\cup\mathcal{W}^{*}$ for every nontrivial
partition $\mathcal{Q}$, then we call $G$ an _$\mathcal{N}$ -good_ graph.

  2. (ii)

If $w(G)\geqslant 0$ and $G/\mathcal{P}\notin\mathcal{N}\cup\mathcal{W}^{*}$
for every partition $\mathcal{P}$, then we call $G$ an _$\mathcal{S}$ -good_
graph.

From the definitions of $\mathcal{N}$-good and $\mathcal{S}$-good graphs, we
note the following.

######  Observation 1.10.

Every $\mathcal{S}$-good graph is also $\mathcal{N}$-good. Every graph in
$\mathcal{W}^{*}$ is $\mathcal{N}$-good (but not $\mathcal{S}$-good).

The second statement requires a bit of case analysis. We illustrate this with
an example: the graph $T_{2,7,7}\in\mathcal{W}^{*}$. Obviously
$T_{2,7,7}\notin\mathcal{N}$. Note that $v(T_{2,7,7})=3$ and
$w(T_{2,7,7})=5>0$ by 1.7. Additionally, every nontrivial partition
$\mathcal{P}$ satisfies $T_{2,7,7}/\mathcal{P}\notin\\{\alpha
K_{2}:\alpha\leqslant 8\\}$ as $\delta(T_{2,7,7})=9$. Furthermore, we also
know that $|\mathcal{P}|=2$ for every nontrivial partition $\mathcal{P}$; thus
$T_{2,7,7}/\mathcal{P}\notin\\{T_{a,b,c}:a+b+c\leqslant 16\\}$. Hence,
$T_{2,7,7}$ is $\mathcal{N}$-good. Similarly, noting that the condition of
$\delta\geqslant 9$ guarantees that $\mu\leqslant 7$ for
$T_{a,b,c}\in\mathcal{W}^{*}$, we can verify that the other graphs in
$\mathcal{W}^{*}$ are also $\mathcal{N}$-good.

We also remark that every $\mathcal{N}$-good (or $\mathcal{S}$-good) graph
satisfies the hypotheses of Theorem 1.11. Thus, this result will facilitate an
inductive proof of Theorem 1.2′, with cases (1)–(3) invoking the inductive
hypothesis, and (4) corresponding to the base case; see Section 3.

For distinct vertices $v,x,y\in V(G)$, to _lift_ a pair of edges $xv,vy\in
E(G)$, we delete edges $xv$ and $vy$, and add a new edge $xy$. Note that
lifting edge pairs may reduce a graph’s edge-connectivity. We call $(xu,uy)$
an _edge-pair_ , $(xu,uv,vy)$ an _edge-triple_ , and $(xu,uv,vw,wy)$ an _edge-
quadruple_ ; in each case, all vertices are distinct. Throughout our proofs we
frequently contract and lift edges. Contracting always preserves planarity, as
does lifting when the edges lie consecutively along a face boundary, which
will always be the case in our proofs.

Now we can state our main result.

######  Theorem 1.11.

Given a planar graph $G$, if $G\neq K_{1}$, $w(G)\geqslant 0$, and
$G/\mathcal{P}\notin\mathcal{N}$ for every partition $\mathcal{P}$, then at
least one of the following statements holds.

  1. (1)

$G$ contains an $\mathcal{N}$-good proper subgraph.

  2. (2)

$G$ admits some lifting such that the resulting graph $G^{\prime}$ contains an
$\mathcal{N}$-good subgraph $H$ and $G^{\prime}/H$ is $\mathcal{S}$-good.

  3. (3)

$G$ admits some lifting at a vertex $v$ such that for the resulting graph
$G^{\prime\prime}$, we know $G^{\prime\prime}-v$ is $\mathcal{S}$-good, and
$G^{\prime\prime}/\mathcal{P}\notin\mathcal{N}$ for every partition
$\mathcal{P}$ of $V(G^{\prime\prime})$.

  4. (4)

$v(G)\leqslant 4$.

As we mentioned above, Theorem 1.11 gives a short proof of Theorem 1.2′. In
addition, it also yields the following result on circular colorings of signed
planar graphs.

######  Theorem 1.12.

For every signed planar graph $(G,\sigma)$ of girth at least $23$, there
exists an $\varepsilon=\varepsilon(G,\sigma)$ such that $(G,\sigma)$ has a
circular $(\frac{16}{7}-\varepsilon)$-coloring.

In fact, we will prove the result in its dual version: for every $23$-edge-
connected signed planar graph $(G,\sigma)$, there is an
$\varepsilon=\varepsilon(G,\sigma)$ such that $(G,\sigma)$ admits a circular
$(\frac{16}{7}-\varepsilon)$-flow.

In the next sections we present the definitions and notation needed to
formally state and prove our remaining results. In Section 2.1, we introduce a
more general definition of orientations. This generality allows us to
transform the problem of circular flow in planar graphs into one about group
connectivity. In Section 2.2, we introduce definitions and results about
circular flows in signed planar graphs. In Section 3 we use the content of
Section 2.1 and Section 2.2 to prove Theorem 1.2′ and Theorem 1.12, assuming
the truth of Theorem 1.11. Finally, Section 4 is the heart of our work. There
we prove Theorem 1.11. We study the properties of a minimum counterexample and
use the discharging method to obtain a contradiction, thus finishing the
proof.

##  2 Preliminaries

Throughout this paper we consider graphs with multiple edges but no loops. For
a graph $G=(V,E)$, we write $v(G)$ and $e(G)$ for its numbers of vertices and
edges. Let $\delta(G)$ be the minimum degree of $G$. For disjoint vertex
subsets $X$ and $Y$ of $V(G)$, we write $[X,Y]$ for the set of edges in $G$
with one endpoint in $X$ and the other endpoint in $Y$, and let
$e_{G}(X,Y):=|[X,Y]|$. Given a vertex subset $X$ of $G$, let
$d(X):=|[X,X^{c}]|$. Further, let $\mu_{G}(uv)$ be the number of parallel
edges between vertices $u$ and $v$. The _multiplicity_ of $G$ is denoted by
$\mu(G)$, where $\mu(G):=\max_{uv\in E(G)}\mu_{G}(uv)$. We use $kG$ to denote
the graph formed by replacing every edge in $G$ with $k$ parallel edges. The
_odd-girth_ of a graph $G$ is the length of its shortest odd cycle. Let $D$ be
an orientation of $G$. An ordered pair $(u,v)$ denotes a directed edge $u\to
v$. And $d_{D}^{-}(v)$ and $d_{D}^{+}(v)$ denote respectively the numbers of
edges directed into and out of $v$. We call $D$ a _strongly connected_
orientation on $G$ if $d_{D}^{+}(S)>0$ and $d_{D}^{-}(S)>0$ for every proper
subset $S\subset V(G)$.

Given a plane graph $G$, let $F(G)$ be the set of faces of $G$ and
$f(G):=|F(G)|$. Given a face $f\in F(G)$, the _degree_ of $f$, denoted $d(f)$,
is the number of edges with which $f$ is incident. A _$k$ -face_ $f$ is a face
with $d(f)=k$ and a _$k^{+}$ -face_ $f$ is a face with $d(f)\geqslant k$. If
two faces are incident with a common edge, then we call them _adjacent_.
Moreover, two faces $f$ and $f^{\prime}$ are _weakly adjacent_ if there is a
face chain $ff_{1}\cdots f_{t}f^{\prime}$, where $f_{i}$ is a $2$-face for
every $i\in\\{1,\ldots,t\\}$.

Let $\mathcal{P}$ be a partition of $V(G)$ with parts
$P_{1},P_{2},\ldots,P_{t}$ and $p_{i}:=|P_{i}|$ for each part. If
$p_{i}\geqslant 2$ for some $i$, then we call $\mathcal{P}$ a _nontrivial_
partition; otherwise, $\mathcal{P}$ is _trivial_. Throughout, we exclude the
partition with a single part $\\{V(G)\\}$. In this work, we say a partition
$\mathcal{P}$ has _type $(k_{1},k_{2},\ast)$_ (or type
$(k_{1}^{+},k_{2}^{+},\ast)$) if $\mathcal{P}=\\{P_{1},P_{2},\ldots,P_{t}\\}$
satisfies that $|P_{1}|\geqslant|P_{2}|\geqslant\cdots\geqslant|P_{t}|$ and
$|P_{1}|=k_{1}$ and $|P_{2}|=k_{2}$ (or $|P_{1}|\geqslant k_{1}$ and
$|P_{2}|\geqslant k_{2}$, respectively).

Let $G$ be a graph and $H$ be a connected subgraph of $G$. We contract $H$ to
form a new vertex $w$. Let $\mathcal{P^{\prime}}$ be a partition of $V(G/H)$
with parts $P_{1},P_{2},\ldots,P_{t}$. If $w\in P_{1}$, then we denote by
$\mathcal{P}$ the partition {$(P_{1}\setminus\\{w\\})\cup
V(H),P_{2},\ldots,P_{t}$}; we call $\mathcal{P}$ the _corresponding_ partition
of $V(G)$.

Given a graph $G=(V,E)$ and a mapping $\sigma:E(G)\to\\{+1,-1\\}$, the pair
$(G,\sigma)$ is called a _signed graph_. An edge is called _positive_ (or
_negative_) if $\sigma(e)=+1$ ($\sigma(e)=-1$, respectively).

###  2.1 Strongly $\mathbb{Z}_{9}$-connected graphs

A modular $k$-orientation is a special case of the general notion of a
$(\mathbb{Z}_{k},\beta)$-orientation, defined as follows. Given a mapping
$\beta:V(G)\to\mathbb{Z}_{k}$, if $\sum_{v\in V(G)}\beta(v)\equiv 0\pmod{k}$,
then we call $\beta$ a _$\mathbb{Z}_{k}$ -boundary_. Given a
$\mathbb{Z}_{k}$-boundary $\beta$ of $G$, a _$(\mathbb{Z}_{k},\beta)$
-orientation_ is an orientation $D$ such that
$d_{D}^{+}(v)-d_{D}^{-}(v)\equiv\beta(v)\pmod{k}$ for every vertex $v\in
V(G)$. A graph $G$ is _strongly $\mathbb{Z}_{k}$-connected_ if for any
$\mathbb{Z}_{k}$-boundary $\beta$, the graph $G$ has a
$(\mathbb{Z}_{k},\beta)$-orientation. Clearly $\beta(v):=0$ for every $v$ is a
$\mathbb{Z}_{k}$-boundary. Thus, every strongly $\mathbb{Z}_{9}$-connected
graph must have a modular $9$-orientation.

Given a positive odd integer $k$, we denote by $\mathcal{SZ}_{k}$ the family
of all graphs that are strongly $\mathbb{Z}_{k}$-connected. Moreover, we have
the following proposition about lifting and contracting for graphs in
$\mathcal{SZ}_{k}$, which we will use frequently.

######  Proposition 2.1.

[2] Let $G$ be a graph and $v\in V(G)$. Let $G^{\prime}$ be a graph formed
from $G$ by lifting some edge pairs at $v$ and $G^{\prime\prime}$ be formed
from $G^{\prime}$ by deleting the vertex $v$.

  1. (i)

For any connected subgraph $H$ of $G$, if $H$ and $G/H$ belong to
$\mathcal{SZ}_{k}$, then $G\in\mathcal{SZ}_{k}$.

  2. (ii)

For any connected subgraph $H$ of $G^{\prime}$, if $H$ and $G^{\prime}/H$
belong to $\mathcal{SZ}_{k}$, then $G\in\mathcal{SZ}_{k}$.

  3. (iii)

If $d_{G^{\prime}}(v)\geqslant k-1$ and $G^{\prime\prime}\in\mathcal{SZ}_{k}$,
then $G^{\prime}\in\mathcal{SZ}_{k}$ and hence $G\in\mathcal{SZ}_{k}$.

  4. (iv)

For any connected subgraph $H$ of $G$, if $H\in\mathcal{SZ}_{k}$ and $G/H$
admits a modular $k$-orientation, then $G$ has a modular $k$-orientation.

All parts of the previous proposition have similar proofs. In each case we fix
a desired boundary $\beta$ for $G$, start with the guaranteed orientation $D$
(with some corresponding boundaries) for the smaller graph ($G/H$,
$G^{\prime}/H$, or $G^{\prime\prime}$), and then extend $D$ to the desired
$(\mathbb{Z}_{k},\beta)$-orientation for $G$ in the obvious way. So we omit
the details.

We will often want to know that various graphs of small order are strongly
$\mathbb{Z}_{9}$-connected. For easy reference, we combine below some results
from [10] and consequences of Proposition 2.1(i).

######  Lemma 2.2.

The following statements about graphs in $\mathcal{SZ}_{9}$ hold.

  1. (i)

[10] The graphs in $\\{\alpha K_{2}:\alpha\geqslant
8\\}\cup\\{T_{a,b,c}:a+b+c\geqslant 16,\delta\geqslant 8\\}\cup\\{G\colon
v(G)=4,e(G)\geqslant 25,\delta(G)\geqslant 8,\mu(G)\leqslant 7\\}$ belong to
$\mathcal{SZ}_{9}$.

  2. (ii)

Every multipath on three vertices with each edge’s multiplicity at least $8$
is in $\mathcal{SZ}_{9}$.

  3. (iii)

Let $G$ be a multigraph on four vertices containing $\alpha K_{2}$ where
$\alpha\geqslant 8$. If $G/\alpha K_{2}$ has at least $16$ edges and
$\delta\geqslant 8$, then $G$ is in $\mathcal{SZ}_{9}$.

For $(ii)$ and $(iii)$, we contract $8K_{2}$ which is in $\mathcal{SZ}_{9}$
and note that the resulting graph is still in $\mathcal{SZ}_{9}$, by
Proposition 2.1(i), we are done.

###  2.2 Strongly connected $(32,\beta)$-orientations of graphs

We also have an equivalent definition about strongly
$\mathbb{Z}_{k}$-connected graphs, which is introduced in [11].

######  Definition 2.3.

  1. (i)

Given a graph $G$ and a mapping $\beta:V(G)\to\\{0,\pm 1,\ldots,\pm k\\}$, if
$\beta(v)\equiv d(v)\pmod{2}$ for every vertex $v$ and $\sum_{v\in
V(G)}\beta(v)\equiv 0\pmod{2k}$, then we call the mapping $\beta$ _a parity-
compliant $\mathbb{Z}_{2k}$-boundary_ (or _$\mathbb{Z}_{2k}$ -pc-boundary_,
for short).

  2. (ii)

Given a $\mathbb{Z}_{2k}$-pc-boundary $\beta$ of $G$, if there exists an
orientation $D$ such that $d_{D}^{+}(v)-d_{D}^{-}(v)\equiv\beta(v)\pmod{2k}$
for every vertex $v$, then we call $D$ a _$(2k,\beta)$ -orientation_.

It has been proved in [8] that a graph $G$ is strongly
$\mathbb{Z}_{k}$-connected if and only if for every $\mathbb{Z}_{2k}$-pc-
boundary $\beta$ of $G$, the graph $G$ admits a $(2k,\beta)$-orientation.
Moreover, if a $(2k,\beta)$-orientation $D$ is strongly connected, then we
call $D$ a _strongly connected $(2k,\beta)$-orientation_. Using these
definitions, we now define a new graph family, which is related to circular
flows in signed graphs.

######  Definition 2.4.

Let $\mathcal{SC}_{k}$ be the family of all graphs that have a strongly
connected $(2k,\beta)$-orientation for every $\mathbb{Z}_{2k}$-pc-boundary
$\beta$.

######  Definition 2.5.

[9] Given positive integers $p$ and $q$ with $p$ being even, a _circular
$\frac{p}{q}$-flow_ in a signed graph $(G,\sigma)$ is a pair $(D,f)$ where $D$
is an orientation on $G$ and $f:E(G)\to\mathbb{Z}$ satisfies the following
conditions.

  1. (i)

For each positive edge $e$, $|f(e)|\in\\{q,\ldots,p-q\\}$;

  2. (ii)

For each negative edge $e$,
$|f(e)|\in\\{0,\ldots,\frac{p}{2}-q\\}\cup\\{\frac{p}{2}+q,\ldots,p-1\\}$;

  3. (iii)

For each vertex $v$, we have $\sum\limits_{(v,w)\in
D}f(vw)-\sum\limits_{(u,v)\in D}f(uv)\equiv 0\pmod{p}$.

The _circular flow index_ of $(G,\sigma)$, denoted by $\phi_{c}(G,\sigma)$, is
the minimum value $\frac{p}{q}$ such that $(G,\sigma)$ admits a circular
$\frac{p}{q}$-flow.

For easy reference, let $\partial_{\\!\scriptscriptstyle
D}f(v):=\sum_{(v,w)\in D}f(vw)-\sum_{(u,v)\in D}f(uv)$. What follows is the
strongest known general result about circular flow value in a signed graph
being less than $\frac{2k}{k-1}$.

######  Theorem 2.6.

[9] Given a signed graph $(G,\sigma)$ and an integer $k\geqslant 2$, if $G$ is
$3k$-edge-connected, then $\phi_{c}(G,\sigma)<\frac{2k}{k-1}$.

As stated in Theorem 1.12, we improve Theorem 2.6 when $(G,\sigma)$ is a
signed planar graph and $k=8$. Specifically, we show that
$\phi_{c}(G,\sigma)<\frac{16}{7}$ whenever $G$ is 23-edge-connected (rather
than 24-edge-connected, as required by Theorem 2.6). Next, we will show the
connection between graphs in $\mathcal{SC}_{2k}$ and signed graphs having
circular $r$-flow with $r<\frac{2k}{k-1}$. Before that, we need the following
lemma.

######  Lemma 2.7.

[9] Given a signed graph $(G,\sigma)$, if $\phi_{c}(G,\sigma)=r$, then every
circular $r$-flow $(D,f)$ has a tight cut, where a tight cut $[X,X^{c}]$ of
$(G,\sigma)$ with respect to $(D,f)$ is defined as follows: for every edge
$uv\in E(G)$ with $u\in X$ and $v\in X^{c}$,

$f(uv)=\left\\{\begin{array}[]{ll}1,&\text{if}\leavevmode\nobreak\
\sigma(uv)=+1\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\ (u,v)\in
D;\\\ r-1,&\text{if}\leavevmode\nobreak\ \sigma(uv)=+1\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ (v,u)\in D;\\\
\frac{r}{2}+1,&\text{if}\leavevmode\nobreak\ \sigma(uv)=-1\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ (u,v)\in D;\\\
\frac{r}{2}-1,&\text{if}\leavevmode\nobreak\ \sigma(uv)=-1\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ (v,u)\in D.\end{array}\right.$

Denote by $p^{+}(v)$ the number of positive edges incident with $v$ in
$(G,\sigma)$ and recall that $2G$ is the graph formed by replacing every edge
in $G$ with $2$ parallel edges.

######  Theorem 2.8.

Given a signed graph $(G,\sigma)$ and a $\mathbb{Z}_{4k}$-pc-boundary $\beta$
such that $\beta(v)\equiv 2k\cdot p^{+}(v)\pmod{4k}$, if $2G$ admits a
strongly connected $(4k,\beta)$-orientation, then
$\phi_{c}(G,\sigma)<\frac{2k}{k-1}$.

###### Proof.

Let $D$ be a strongly connected $(4k,\beta)$-orientation on $2G$ with
$\beta(v)\equiv 2k\cdot p^{+}(v)\pmod{4k}$. For every edge $e\in E(G)$, we
denote by $\\{e_{1},e_{2}\\}$ the parallel edges in $E(2G)$ corresponding to
$e$. Let $D_{1}$ be an auxiliary orientation on $G$. We first define a mapping
$f_{1}$ on $E(G)$ such that $f_{1}(e)=I(e_{1})+I(e_{2})$, where $I$ is an
indicator function on $E(2G)$ such that $I(e_{i})=1$ if $D(e_{i})=D_{1}(e)$
and $I(e_{i})=-1$ otherwise. It is easy to see that $f_{1}(e)\in\\{-2,0,2\\}$
and $\partial_{\\!\scriptscriptstyle
D_{1}}f_{1}(v)=d_{D}^{+}(v)-d_{D}^{-}(v)\equiv\beta(v)\pmod{4k}$ for every
vertex $v\in V(G)$. We then define another mapping
$f_{2}:E(G,\sigma)\to\\{0,2k\\}$ such that $f_{2}(e)=2k$ if $e$ is positive
and $f_{2}(e)=0$ otherwise. Thus $\partial_{\\!\scriptscriptstyle
D_{1}}f_{2}(v)\equiv 2k\cdot p^{+}(v)\pmod{4k}$ for each vertex $v\in V(G)$.
Let $f:=f_{1}+f_{2}$. We know that in $(G,\sigma)$,
$f(e)\in\\{2k-2,2k,2k+2\\}$ for every positive edge $e$ and
$f(e)\in\\{-2,0,2\\}$ for every negative edge $e$. Moreover,
$\partial_{\\!\scriptscriptstyle D_{1}}f(v)=\partial_{\\!\scriptscriptstyle
D_{1}}f_{1}(v)+\partial_{\\!\scriptscriptstyle
D_{1}}f_{2}(v)\equiv\beta(v)+2k\cdot p^{+}(v)\equiv 0\pmod{4k}$. Thus,
$(D_{1},f)$ is a circular $\frac{4k}{2k-2}$-flow in $(G,\sigma)$, which
implies $\phi_{c}(G,\sigma)\leqslant\frac{4k}{2k-2}=\frac{2k}{k-1}$.

To show that $\phi_{c}(G,\sigma)<\frac{2k}{k-1}$, suppose to the contrary that
$\phi_{c}(G,\sigma)=\frac{2k}{k-1}$. By Lemma 2.7, every circular
$\frac{2k}{k-1}$-flow of $(G,\sigma)$ has a tight cut. In particular, there is
a tight cut $[X,X^{c}]$ with respect to $(D_{1},f)$. By the definition of
tight cuts, for every edge $e=uv\in[X,X^{c}]$ with $u\in X$ and $v\in X^{c}$,
when $\sigma(e)=+1$, $f(e)=2k-2$ if $(u,v)\in D_{1}$ and $f(e)=2k+2$ if
$(v,u)\in D_{1}$; when $\sigma(e)=-1$, $f(e)=-2$ if $(u,v)\in D_{1}$ and
$f(e)=2$ if $(v,u)\in D_{1}$. By the definitions of mappings $I$ and $f$, if
$f(e)=2k+2$ or $f(e)=2$, then $e_{1}$ and $e_{2}$ have the same direction in
$D$, and $e$ is oriented in $D_{1}$ the same as the $e_{i}$’s in $D$; if
$f(e)=2k-2$ or $f(e)=-2$, then $e_{1}$ and $e_{2}$ have the same direction in
$D$, and $e$ is oriented in $D_{1}$ opposite to the $e_{i}$’s in $D$.
Therefore, under the orientation $D$, all the edges of $E(2G)$ are oriented
from $X^{c}$ to $X$; thus $D$ is not strongly connected (as $d_{D}^{+}(X)=0$),
which is a contradiction. Hence $\phi_{c}(G,\sigma)<\frac{2k}{k-1}$. ∎

The conclusion of Theorem 1.12 is the conclusion of Theorem 2.8, with $k=8$.
So it suffices to prove that $2G\in\mathcal{SC}_{16}$ for every $23$-edge-
connected planar graph $G$. Hence, the graph family $\mathcal{SC}_{k}$ plays
an important role.

Given a graph $G$ and its connected subgraph $H$, let $G^{\prime}:=G/H$ and
let $w$ denote the new vertex formed by contracting $H$. For every
$\mathbb{Z}_{2k}$-pc-boundary $\beta$ of $G$, a mapping
$\beta^{\prime}:V(G^{\prime})\to\\{0,\pm 1,\ldots,\pm k\\}$ is defined as
follows: $\beta^{\prime}(w):\equiv\sum_{v\in V(H)}\beta(v)\pmod{2k}$ and
$\beta^{\prime}(v):=\beta(v)$ for every $v\in V(G^{\prime})\backslash\\{w\\}$.
Note that $\beta^{\prime}$ is a $\mathbb{Z}_{2k}$-pc-boundary of $G^{\prime}$.

Fix a graph $G$ and its subgraph $H$, a $\mathbb{Z}_{2k}$-pc-boundary $\beta$
of $G$, and $\beta^{\prime}$ of $G^{\prime}$ as above. Note that $G$ admits a
$(2k,\beta)$-orientation if $G^{\prime}$ admits a
$(2k,\beta^{\prime})$-orientation and $H$ admits a
$(2k,\beta^{\prime\prime})$-orientation for every $\mathbb{Z}_{2k}$-pc-
boundary $\beta^{\prime\prime}$ of $H$. And if these orientations for
$G^{\prime}$ and $H$ are both strongly connected, then so is the orientation
for $G$. Thus, if $H\in\mathcal{SC}_{k}$ and $G/H\in\mathcal{SC}_{k}$, then
also $G\in\mathcal{SC}_{k}$. To push this idea further, we seek the largest
class of graphs $H$ to which it applies. This motivates the following two
definitions, similar to those in [4].

######  Definition 2.9.

Let $G$ be a graph. If $H\subseteq G$ and there exist distinct vertices
$x,y\in V(H)$ such that we have an $(x,y)$-path in $G-E(H)$, then we call $G$
a _nice supergraph_ of $H$.

######  Definition 2.10.

Let $k$ be a positive integer. Given a graph $H$ and its nice supergraph $G$,
we call $H$ _weakly contractible_ if for every $\mathbb{Z}_{2k}$-pc-boundary
$\beta$ of $G$, every strongly connected $(2k,\beta^{\prime})$-orientation of
$G/H$ can be extended to a strongly connected $(2k,\beta)$-orientation of $G$.

Let $\mathcal{W}_{k}$ be the family of all graphs that are weakly
contractible.

From the definitions, it is straightforward to check that
$\mathcal{SC}_{k}\subseteq\mathcal{W}_{k}$. Similar to the connection between
the graph families $\mathcal{W}_{3}$ and $\mathcal{SC}_{3}$ shown in [4], we
have the following proposition about the graph families $\mathcal{W}_{k}$ and
$\mathcal{SC}_{k}$.

######  Proposition 2.11.

A graph $H\in\mathcal{W}_{k}$ if and only if $H+xy\in\mathcal{SC}_{k}$ for all
distinct $x,y\in V(H)$.

Note that we allow graphs to have multiple edges, so possibly $xy\in e(H)$. As
an immediate corollary of the above proposition, we have the following.

######  Proposition 2.12.

  1. (1)

If $G$ contains a Hamiltonian cycle $C$ such that $G-E(C)\in\mathcal{SZ}_{k}$,
then $G\in\mathcal{SC}_{k}$.

  2. (2)

If for any two distinct vertices $x,y$ of a graph $G$, there is a Hamiltonian
path $P_{xy}$ such that $G-E(P_{xy})\in\mathcal{SZ}_{k}$, then
$G\in\mathcal{W}_{k}$.

###### Proof.

(1) If $D$ is a $(2k,\beta)$-orientation, for some given boundary $\beta$,
then adding a cyclicly oriented Hamiltonian cycle yields a strongly connected
digraph that is also a $(2k,\beta)$-orientation. (2) follows directly from (1)
by Proposition 2.11. ∎

For our proofs in the following sections, we will also make use of the next
proposition. Both its statement and its proof are analogous to those of
Proposition 2.1.

######  Proposition 2.13.

Given a graph $G$ and a vertex $v\in V(G)$, let $G^{\prime}$ be a graph formed
from $G$ by lifting some edge pairs at $v$ and let $G^{\prime\prime}$ be a
graph formed from $G^{\prime}$ by deleting the vertex $v$. Then the following
statements hold.

  1. (i)

Given a connected subgraph $H$ of $G$, if $H\in\mathcal{W}_{k}$ and
$G/H\in\mathcal{SC}_{k}$, then $G\in\mathcal{SC}_{k}$.

  2. (ii)

Given a connected subgraph $H$ of $G^{\prime}$, if $H\in\mathcal{W}_{k}$ and
$G^{\prime}/H\in\mathcal{SC}_{k}$, then $G\in\mathcal{SC}_{k}$.

  3. (iii)

If $d_{G^{\prime}}(v)\geqslant k$ and $G^{\prime\prime}\in\mathcal{SC}_{k}$,
then $G\in\mathcal{SC}_{k}$.

In [10], all graphs in $\\{15K_{2}\\}\cup\\{T_{a,b,c}:a+b+c=30,\delta\geqslant
15\\}\cup\\{G\colon v(G)=4,e(G)=46,\delta(G)\geqslant 15,\mu(G)\leqslant
15\\}$ were shown to belong to $\mathcal{SZ}_{16}$. By applying Proposition
2.12 and Proposition 2.13(i), we have the following results.

######  Lemma 2.14.

  1. (i)

The graphs in $\\{16K_{2}\\}\cup\\{T_{a,b,c}:a+b+c=32,\delta\geqslant
17\\}\cup\\{G\colon v(G)=4,e(G)=49,\delta(G)\geqslant 17,\mu(G)\leqslant
16\\}$ belong to $\mathcal{W}_{16}$.

  2. (ii)

The graphs in $\\{\alpha K_{2}:\alpha\geqslant
17\\}\cup\\{T_{a,b,c}:a+b+c\geqslant 33,\delta\geqslant 17\\}\cup\\{G\colon
v(G)=4,e(G)\geqslant 50,\delta(G)\geqslant 17,\mu(G)\leqslant 16\\}$ belong to
$\mathcal{SC}_{16}$.

  3. (iii)

Every multipath on three vertices with each edge’s multiplicity at least $17$
is in $\mathcal{SC}_{16}$.

  4. (iv)

Let $G$ be a multigraph on four vertices containing $\alpha K_{2}$ where
$\alpha\geqslant 17$. If $G/\alpha K_{2}$ has at least $33$ edges and
$\delta\geqslant 17$, then $G$ is in $\mathcal{SC}_{16}$.

###### Proof.

For graphs in (i), we delete an arbitrary Hamiltonian path; for graphs in
(ii), we delete an arbitrary Hamiltonian cycle. Note that each of the
resulting graphs is in $\\{15K_{2}\\}\cup\\{T_{a,b,c}:a+b+c=30,\delta\geqslant
15\\}\cup\\{G\colon v(G)=4,e(G)=46,\delta(G)\geqslant 15,\mu(G)\leqslant
15\\}\subset\mathcal{SZ}_{16}$. So (i) and (ii) hold by Proposition 2.12.

For (iii), let $P$ be a multipath with vertex set $\\{x,y,z\\}$ and
$\mu(xy)\geqslant 17$ and $\mu(yz)\geqslant 17$. By (ii), the two-vertex
subgraph $P_{xy}$ induced by $x$ and $y$ is in
$\mathcal{SC}_{16}(\subset\mathcal{W}_{16})$ and, moreover,
$P/P_{xy}\in\mathcal{SC}_{16}$. By Proposition 2.13(i),
$P\in\mathcal{SC}_{16}$.

For (iv), note that $G$ contains a subgraph $\alpha K_{2}$ which belongs to
$\mathcal{SC}_{16}$. Moreover, $G/\alpha K_{2}$ has three vertices and at
least $33$ edges, and $\delta(G/\alpha K_{2})\geqslant 17$. By (ii) and (iii),
$G/\alpha K_{2}$ also belongs to $\mathcal{SC}_{16}$. By Proposition 2.13(i),
$G\in\mathcal{SC}_{16}$. ∎

##  3 Proofs of Theorem 1.2′ and Theorem 1.12

In this section, we assume the truth of Theorem 1.11 and use it to prove
Theorem 1.2′ and Theorem 1.12. We remark that every graph $G$ that is
$\mathcal{N}$-good or $\mathcal{S}$-good satisfies the hypotheses of Theorem
1.11; thus, such a graph $G$ also satisfies its conclusion.

Now assuming that Theorem 1.11 is true, we first obtain Theorem 3.1 below.
Part (2) immediately implies (the flow version of) Theorem 1.12; part (1)
implies a slight weakening of Theorem 1.2′, which requires edge-connectivity
at least $23$, rather than odd-edge-connectivity at least $23$. Proving the
final version of that result requires one more trick, which we present at the
end of this section.

######  Theorem 3.1.

Let $G$ be a planar graph such that $G\neq K_{1}$ and $w(G)\geqslant 0$.

  1. (1)

If $G/\mathcal{P}\not\in\mathcal{N}$ for every partition $\mathcal{P}$, then
$G\in\mathcal{SZ}_{9}$.

  2. (2)

If $G/\mathcal{P}\notin\mathcal{W}^{*}\cup\mathcal{N}$ for every partition
$\mathcal{P}$ (that is, $G$ is $\mathcal{S}$-good), then
$2G\in\mathcal{SC}_{16}$.

This result is sharp in the following sense. For each $G\in\mathcal{N}$, it is
straightforward to construct a boundary showing that
$G\notin\mathcal{SZ}_{9}$. Similarly, for each
$G\in\mathcal{W}^{*}\cup\mathcal{N}$ it is straightforward to construct a
boundary showing that $2G\notin\mathcal{SC}_{16}$.

###### Proof.

(1) Assume to the contrary that $G$ is a minimum counterexample with
$v(G)+e(G)$ being minimized. Note that $G$ satisfies all the hypotheses of
Theorem 1.11 and thus its conclusion must hold for $G$. We consider the four
cases.

  * •

If Theorem 1.11(1) holds, then $G$ contains an $\mathcal{N}$-good proper
subgraph $H$. By the definition of $\mathcal{N}$-good graphs,
$H/\mathcal{P}\notin\mathcal{N}$ for every partition $\mathcal{P}$ of $V(H)$.
As $H$ is a proper subgraph of $G$, by the minimality of $G$, the graph
$H\in\mathcal{SZ}_{9}$. Furthermore, note that $w(G/H)\geqslant 0$, that $G/H$
has no partition $\mathcal{P}$ such that $(G/H)/\mathcal{P}\in\mathcal{N}$,
and that $G/H$ has fewer vertices than $G$ (as $v(H)\geqslant 2$). Again since
$G$ is a minimal counterexample, $G/H\in\mathcal{SZ}_{9}$. By Proposition
2.1(i), $G\in\mathcal{SZ}_{9}$, a contradiction.

  * •

If Theorem 1.11(2) holds, then the resulting graph $G^{\prime}$ formed by some
lifting contains an $\mathcal{N}$-good subgraph $H$ and $G^{\prime}/H$ is
$\mathcal{S}$-good. It is easily observed that each of $H$ and $G^{\prime}/H$
satisfies the conditions of this theorem but has fewer edges than $G$. Hence
both $H$ and $G^{\prime}/H$ belong to $\mathcal{SZ}_{9}$. By Proposition
2.1(ii), $G\in\mathcal{SZ}_{9}$, a contradiction.

  * •

If Theorem 1.11(3) holds, then the resulting graph $G^{\prime\prime}$ formed
from $G$ by lifting at a vertex $v$ satisfies that $G^{\prime\prime}-v$ is
$\mathcal{S}$-good, and also that
$G^{\prime\prime}/\mathcal{P}\notin\mathcal{N}$ for every partition
$\mathcal{P}$ of $V(G^{\prime\prime})$. We first claim that
$G^{\prime\prime}-v\in\mathcal{SZ}_{9}$ because it satisfies the conditions of
this theorem (as it is $\mathcal{S}$-good) but has fewer vertices than $G$.
Since $G^{\prime\prime}/\mathcal{P}\notin\mathcal{N}$ for every partition
$\mathcal{P}$ of $V(G^{\prime\prime})$, we know that
$d_{G^{\prime\prime}}(v)\geqslant 8$. By Proposition 2.1(iii),
$G\in\mathcal{SZ}_{9}$, which is a contradiction.

  * •

If Theorem 1.11(4) holds, then we assume that $2\leqslant v(G)\leqslant 4$. We
will describe $G$ explicitly and use Lemma 2.2 to show that
$G\in\mathcal{SZ}_{9}$. That $G/\mathcal{P}\notin\\{\alpha
K_{2}:\alpha\leqslant 7\\}\subset\mathcal{N}$ for every partition
$\mathcal{P}$ implies that $\delta(G)\geqslant 8$. If $v(G)=2$, then $G$ is
$\alpha K_{2}$ with $\alpha\geqslant 8$. If $v(G)=3$, then $G$ is either a
multipath with $\delta\geqslant 8$ or a multitriangle $T_{a,b,c}$ with
$a+b+c\geqslant 16$ as $G/\mathcal{P}\notin\\{T_{a,b,c},a+b+c\leqslant 15\\}$
for every partition $\mathcal{P}$. If $v(G)=4$, then $e(G)\geqslant 25$ since
$w(G)\geqslant 0$. Furthermore, if $G$ contains $\alpha K_{2}$ with
$\alpha\geqslant 8$, then $G/\alpha K_{2}$ has at least $16$ edges since
$G/\alpha K_{2}\notin\\{T_{a,b,c},a+b+c\leqslant 15\\}$ and $G/\alpha K_{2}$
has minimum degree at least $8$; if $\mu(G)\leqslant 7$, then $G$ satisfies
that $e(G)\geqslant 25$, $\mu(G)\leqslant 7$, and $\delta(G)\geqslant 8$.
According to Lemma 2.2, each of the graphs $G$ described above belongs to
$\mathcal{SZ}_{9}$.

(2) Let $G$ be a counterexample minimizing $v(G)+e(G)$. It means
$2G\notin\mathcal{SC}_{16}$. Note that $G$ is $\mathcal{S}$-good and thus the
conclusion of Theorem 1.11 holds for $G$. Similarly we consider four cases,
each leading to the contradiction that $2G\in\mathcal{SC}_{16}$.

  * •

If Theorem 1.11(1) holds, then $G$ contains an $\mathcal{N}$-good proper
subgraph $H$. By hypothesis, $w(G/H)\geqslant w(G)\geqslant 0$; and also
$(G/H)/\mathcal{P}\notin\mathcal{N}\cup\mathcal{W}^{*}$ for every partition
$\mathcal{P}$. Thus, $G/H$ is $\mathcal{S}$-good. So
$(2G)/(2H)\in\mathcal{SC}_{16}$, by the minimality of $G$. If
$H/\mathcal{P}\notin\mathcal{W}^{*}$ for every partition $\mathcal{P}$, then
$H$ is $\mathcal{S}$-good; thus the minimality of $G$ gives
$2H\in\mathcal{SC}_{16}\subseteq\mathcal{W}_{16}$. If
$H/\mathcal{P}_{0}\in\mathcal{W}^{*}$ for the trivial partition
$\mathcal{P}_{0}$, then $H\in\mathcal{W}^{*}$. In this case
$2H\in\\{16K_{2}\\}\cup\\{T_{a,b,c}:a+b+c=32,\delta\geqslant 18\\}$ and
$2H\in\mathcal{W}_{16}$ by Lemma 2.14(i). Now by Proposition 2.13(i) we get
$2G\in\mathcal{SC}_{16}$, a contradiction.

  * •

If Theorem 1.11(2) holds, then $G^{\prime}/H$ is $\mathcal{S}$-good; the
minimality of $G$ gives
$(2G^{\prime})/(2H)\in\mathcal{SC}_{16}\subseteq\mathcal{W}_{16}$. Similarly,
if $H/\mathcal{P}\notin\mathcal{W}^{*}$ for every partition $\mathcal{P}$,
then $2H\in\mathcal{SC}_{16}$. But if $H/\mathcal{P}_{0}\in\mathcal{W}^{*}$
for the trivial partition $\mathcal{P}_{0}$, then $H\in\mathcal{W}^{*}$ by
definition; as above, $2H\in\mathcal{W}_{16}$. In both cases, by Proposition
2.13(ii) we get $2G\in\mathcal{SC}_{16}$, a contradiction.

  * •

If Theorem 1.11(3) holds, then $G^{\prime\prime}-v$ is $\mathcal{S}$-good.
Hence $2(G^{\prime\prime}-v)\in\mathcal{SC}_{16}$, by the minimality of $G$.
Since $G^{\prime\prime}/\mathcal{P}\notin\mathcal{N}$ for every partition
$\mathcal{P}$, we have $d_{2G^{\prime\prime}}(v)\geqslant 16$. Thus by
Proposition 2.13(iii) we get $2G\in\mathcal{SC}_{16}$, a contradiction.

  * •

If Theorem 1.11(4) holds, then $2\leqslant v(G)\leqslant 4$. We will describe
$G$ explicitly and use Lemma 2.14 to show that $2G\in\mathcal{SC}_{16}$. Since
$G/\mathcal{P}\notin\mathcal{W}^{*}\cup\mathcal{N}$ for every partition
$\mathcal{P}$, $\delta(G)\geqslant 9$. If $v(G)=2$, then $2G=\alpha K_{2}$
with $\alpha\geqslant 18$. If $v(G)=3$, then $2G$ is either a multipath with
$\delta(2G)\geqslant 18$ or a multitriangle $T_{a,b,c}$ with $a+b+c\geqslant
34$ since $G/\mathcal{P}\notin\\{T_{a,b,c},a+b+c\leqslant 16\\}$ for every
partition $\mathcal{P}$. If $v(G)=4$, then $e(2G)=2e(G)\geqslant 50$ since
$w(G)\geqslant 0$. If $2G$ has a subgraph $\alpha K_{2}$ with $\alpha\geqslant
17$, then $2G/\alpha K_{2}$ contains at least $34$ edges because $G$ has no
partition $\mathcal{P}$ such that $G/\mathcal{P}\in\\{T_{a,b,c},a+b+c\leqslant
16\\}$ and, furthermore, such $2G/\alpha K_{2}$ has minimum degree at least
$18$. If $\mu(2G)\leqslant 16$, then $2G$ satisfies that $e(2G)\geqslant 50$,
$\delta(2G)\geqslant 18$ and $\mu(2G)\leqslant 16$. By Lemma 2.14, in each
case $2G\in\mathcal{SC}_{16}$.

This completes the proof of the theorem. ∎

######  Corollary 3.2.

If $G$ is a 23-edge-connected planar graph, then:

  1. (1)

$G\in\mathcal{SZ}_{9}$; and

  2. (2)

$2G\in\mathcal{SC}_{16}$.

###### Proof.

For (1), since $G$ is $23$-edge-connected, for every partition $\mathcal{P}$
with parts $P_{1},P_{2},\ldots,P_{t}$, we have $d_{G}(P_{i})\geqslant 23$ for
all $i\in[t]$. Thus $w(G)\geqslant 23t-23t+42=42$, which implies that
$G/\mathcal{P}\notin\mathcal{N}$ for every partition $\mathcal{P}$ by 1.8(1).
By Theorem 3.1(1), $G\in\mathcal{SZ}_{9}$.

For (2), since $G$ is $23$-edge-connected, again $w(G)\geqslant 42$ and
$G/\mathcal{P}\notin\mathcal{W}^{*}\cup\mathcal{N}$ for every partition
$\mathcal{P}$ by 1.8(2). It follows from Theorem 3.1(2) that
$2G\in\mathcal{SC}_{16}$. ∎

Theorem 1.12 is a straightforward consequence of the above result. Corollary
3.2(2) implies that $2G$ admits a strongly connected $(32,\beta)$-orientation
for every given $\mathbb{Z}_{32}$-pc-boundary $\beta$ with $\beta(v)\equiv
16\cdot p^{+}(v)\pmod{32}$. By Theorem 2.8, for every signature $\sigma$ of
$G$ we get $\phi_{c}(G,\sigma)<\frac{16}{7}$.

To obtain Theorem 1.2′, we need Zhang’s splitting lemma [18] below.

######  Lemma 3.3.

_[18]_ Let $G=(V,E)$ be a graph with odd-edge-connectivity $\lambda$. Assume
there is a vertex $v\in V(G)$ such that $d(v)\notin\\{2,\lambda\\}$.
Arbitrarily label the edges of $G$ incident with $v$ as
$\\{e_{1},e_{2},\ldots,e_{d(v)}\\}$. Then there is an integer
$i\in\\{1,2,\ldots,d(v)\\}$ such that the new graph formed from $G$ by
splitting $e_{i}$ and $e_{i+1}$ (indices $i,i+1$ are taken modulo $d(v)$) away
from $v$ remains of odd-edge-connectivity $\lambda$.

_Proof of Theorem 1.2 ′_. We will prove that every odd-$23$-edge-connected
planar graph admits a modular $9$-orientation. Assume to the contrary that $G$
is a counterexample minimizing $v(G)$. If $\delta(G)<23$, then there exists
$v$ with $d(v)<23$ and $d(v)$ even. We label the edges incident to $v$ in
their (cyclic) order around $v$ in the plane embedding of $G$. By Lemma 3.3,
we can lift off all of these edges from $v$ (in pairs) such that the resulting
graph $G^{\prime}$ is again odd-23-edge-connected. Thus, $G^{\prime}$ is a
smaller counterexample, contradicting our choice of $G$. Hence, we assume that
$\delta(G)\geqslant 23$.

If $G$ is $23$-edge-connected, then Corollary 3.2(1) implies that
$G\in\mathcal{SZ}_{9}$; in particular, $G$ admits a modular $9$-orientation.
Thus we assume that $[X,X^{c}]$ is an edge-cut where $d(X)<23$ and $|X|$ is
minimized. Note that $|X|\geqslant 2$ and for every subset
$X^{\prime}\subsetneq X$, $d(X^{\prime})\geqslant 23$. Let $H:=G[X]$. By the
minimality of $X$, $H$ is connected. For every partition $\mathcal{Q}$ of
$V(H)$ with parts $Q_{1},Q_{2},\ldots,Q_{t}$, we have
$w_{H}(\mathcal{Q})=\sum_{i=1}^{t}d_{H}(Q_{i})-23t+42=(\sum_{i=1}^{t}d_{G}(Q_{i})-d_{G}(X))-23t+42\geqslant
23t-23-23t+42=19$. Thus $w(H)\geqslant 19$, which implies that
$H/\mathcal{P}\notin\mathcal{N}$ for every partition $\mathcal{P}$ by 1.8(1).
By Theorem 3.1(1), $H\in\mathcal{SZ}_{9}$. As $G$ is a minimum counterexample
and $v(H)=|X|\geqslant 2$, $G/H$ admits a modular $9$-orientation. Hence, $G$
has a modular $9$-orientation by Proposition 2.1(iv), a contradiction. ∎

##  4 Main theorem

This section is devoted to proving Theorem 1.11. Below, we recall its
statement. But first we remind the reader of the definition of the weight
function, given in Equation 1, as well as the notions of $\mathcal{N}$-good
and $\mathcal{S}$-good from Definition 1.9.

Theorem 1.11. Given a planar graph $G$, if $G\neq K_{1}$, $w(G)\geqslant 0$,
and $G/\mathcal{P}\notin\mathcal{N}$ for any partition $\mathcal{P}$, then at
least one of the following 4 statements holds.

  1. (1)

$G$ contains an $\mathcal{N}$-good proper subgraph.

  2. (2)

$G$ admits some lifting such that the resulting graph $G^{\prime}$ contains an
$\mathcal{N}$-good subgraph $H$ and $G^{\prime}/H$ is $\mathcal{S}$-good.

  3. (3)

$G$ admits some lifting at a vertex $v$ such that for the resulting graph
$G^{\prime\prime}$ we know $G^{\prime\prime}-v$ is $\mathcal{S}$-good, and
$G^{\prime\prime}/\mathcal{P}\notin\mathcal{N}$ for every partition
$\mathcal{P}$ of $V(G^{\prime\prime})$.

  4. (4)

$v(G)\leqslant 4$.

In the rest of the proof we will frequently be reasoning about graphs that are
$\mathcal{N}$-good or $\mathcal{S}$-good. So it is helpful to recall the
following observation.

1.10. Every $\mathcal{S}$-good graph is also $\mathcal{N}$-good. Every graph
in $\mathcal{W}^{*}$ is $\mathcal{N}$-good (but not $\mathcal{S}$-good).

We also introduce another $\mathcal{N}$-good graph: $6C_{4}^{+}$, which is
used in the next subsection. We write $6C_{4}^{+}$ to denote the graph formed
from $6C_{4}$ by adding one more parallel edge between two adjacent vertices.
Clearly, $v(6C_{4}^{+})=4$, $e(6C_{4}^{+})=25$, and $\delta(6C_{4}^{+})=12$.
Furthermore, by 1.7, $w(6C_{4}^{+})=2e(6C_{4}^{+})-50=0$. Obviously
$6C_{4}^{+}\notin\mathcal{N}$. For every nontrivial partition $\mathcal{P}$ of
$6C_{4}^{+}$, we have $6C_{4}^{+}/\mathcal{P}\in\\{\alpha
K_{2}:\alpha\geqslant 12\\}\cup\\{T_{a,b,c}:a+b+c\geqslant 18,\delta\geqslant
12\\}$. Thus, $6C_{4}^{+}$ is an $\mathcal{N}$-good graph.

To prove Theorem 1.11, we assume the result is false and let $G$ be a
counterexample minimizing $v(G)+e(G)$. Note that $v(G)\geqslant 5$ and $G$
contains no $\mathcal{N}$-good proper subgraph. In the next subsection, we
prove our lower bound on the edge connectivity of this minimal counterexample,
and find some configurations forbidden in $G$. Finally, in Section 4.2 we use
the discharging method to complete the proof of Theorem 1.11.

###  4.1 Forbidden configurations

Recall that our minimal counterexample $G$ satisfies $w(G)\geqslant 0$. Next
we prove a useful lemma, called the _gap lemma_ , indicating that for any
nontrivial partition $\mathcal{P}$ of $V(G)$ the weight value
$w_{G}(\mathcal{P})$ is much larger than $0$. The gap lemma allows us to lift
edge pairs and guarantee that the resulting graph still has a non-negative
weight. We use this lemma frequently in the rest of the proof. We recall that
a partition $\mathcal{P}$ _has type $(p_{1}^{+},p_{2}^{+},*)$_ when
$\mathcal{P}$ has parts $P_{1},P_{2},\ldots$ with $|P_{1}|\geqslant p_{1}$,
$|P_{2}|\geqslant p_{2}$, and all other parts (if they exist) have no
requirement on their sizes.

######  Lemma 4.1 (Gap Lemma).

Let $\mathcal{P}$ be a nontrivial partition of $V(G)$ with parts
$P_{1},P_{2},\ldots,P_{t}$ such that
$|P_{1}|\geqslant|P_{2}|\geqslant\cdots\geqslant|P_{t}|$.

  1. (a)

if $\mathcal{P}$ has type $(2^{+},1^{+},*)$, then $w_{G}(\mathcal{P})\geqslant
9$;

  2. (b)

if $\mathcal{P}$ has type $(3^{+},1^{+},*)$, then $w_{G}(\mathcal{P})\geqslant
16$;

  3. (c)

if $\mathcal{P}$ has type $(2^{+},2^{+},*)$, then $w_{G}(\mathcal{P})\geqslant
18$;

  4. (d)

if $\mathcal{P}$ has type $(4^{+},1^{+},*)$, then $w_{G}(\mathcal{P})\geqslant
20$;

  5. (e)

if $\mathcal{P}$ has type $(3^{+},2^{+},*)$, then $w_{G}(\mathcal{P})\geqslant
25$;

  6. (f)

if $\mathcal{P}$ has type $(3^{+},3^{+},*)$, then $w_{G}(\mathcal{P})\geqslant
32$.

###### Proof.

Let $H:=G[P_{1}]$ and let $\mathcal{Q}$ be a partition of $V(H)$ with parts
$Q_{1},Q_{2},\ldots,Q_{s}$. Since $\mathcal{Q}\cup\mathcal{P}\backslash P_{1}$
is a refinement of $\mathcal{P}$, we have

$\displaystyle w_{G}(\mathcal{Q}\cup\mathcal{P}\backslash P_{1})$
$\displaystyle=\sum\limits_{k=1}^{s}d_{G}(Q_{k})+\sum\limits_{i=2}^{t}d_{G}(P_{i})-23(t-1+s)+42$
$\displaystyle=\Big{(}\sum\limits_{k=1}^{s}d_{H}(Q_{k})+d_{G}(P_{1})\Big{)}+\sum\limits_{i=2}^{t}d_{G}(P_{i})-23(t-1+s)+42$
$\displaystyle=\Big{(}\sum\limits_{k=1}^{s}d_{H}(Q_{k})-23s+42\Big{)}+\Big{(}\sum\limits_{i=1}^{t}d_{G}(P_{i})-23t+42\Big{)}+23-42$
$\displaystyle=w_{H}(\mathcal{Q})+w_{G}(\mathcal{P})-19.$

Thus,

$w_{H}(\mathcal{Q})=w_{G}(\mathcal{Q}\cup\mathcal{P}\setminus
P_{1})-w_{G}(\mathcal{P})+19.$ (2)

Each of (a)–(f) is proved in the same way. We assume the statement is false
and use Equation (2) to show that $H$ is an $\mathcal{N}$-good subgraph of
$G$. Thus, Theorem 1.11(1) holds, so $G$ is not a counterexample after all, a
contradiction. We use earlier parts of the lemma to prove later parts, which
is why we phrase many of its parts in such generality even though many of
these (more general) cases are subsumed by later parts.

For (a), suppose $\mathcal{P}$ is a partition with type $(2^{+},1^{+},\ast)$
such that $w_{G}(\mathcal{P})\leqslant 8$ and $|\mathcal{P}|$ is maximized.
For the trivial partition $\mathcal{Q}_{0}$ of $V(H)$, by Equation 2,
$w_{H}(\mathcal{Q}_{0})=w_{G}(\mathcal{Q}_{0}\cup\mathcal{P}\backslash
P_{1})-w_{G}(\mathcal{P})+19\geqslant w(G)-w_{G}(\mathcal{P})+19\geqslant
0-8+19=11$. Thus 1.8(1) implies $H/\mathcal{Q}_{0}\notin\mathcal{N}$. Every
nontrivial partition $\mathcal{Q}$ has type $(2^{+},1^{+},\ast)$ and
$\mathcal{Q}\cup\mathcal{P}\backslash P_{1}$ (as a partition of $V(G)$) also
has type $(2^{+},1^{+},\ast)$ with $|\mathcal{Q}\cup\mathcal{P}\backslash
P_{1}|>|\mathcal{P}|$. By the maximality of $|\mathcal{P}|$, we have
$w_{G}(\mathcal{Q}\cup\mathcal{P}\backslash P_{1})\geqslant 9$. Thus,
$w_{H}(\mathcal{Q})=w_{G}(\mathcal{Q}\cup\mathcal{P}\setminus
P_{1})-w_{G}(\mathcal{P})+19\geqslant 9-8+19=20$ so 1.8(2) gives
$H/\mathcal{Q}\notin\mathcal{N}\cup\mathcal{W}^{*}$. Combining the cases
above, we get $w(H)\geqslant 11$. Since $H/\mathcal{Q}_{0}\notin\mathcal{N}$
and $H/\mathcal{Q}\notin\mathcal{N}\cup\mathcal{W}^{*}$ for all other
partitions $\mathcal{Q}$, by definition $H$ is an $\mathcal{N}$-good subgraph
of $G$.

For (b), suppose $\mathcal{P}$ is a partition with type $(3^{+},1^{+},*)$ such
that $w_{G}(\mathcal{P})\leqslant 15$. We consider a partition $\mathcal{Q}$
of $V(H)$. If $\mathcal{Q}$ is trivial, then Equation 2 gives
$w_{H}(\mathcal{Q})\geqslant 0-15+19=4$. As the trivial partition has at least
$3$ parts, 1.8(3) implies $H/\mathcal{Q}\notin\mathcal{N}$. Otherwise
$\mathcal{Q}$ has type $(2^{+},1^{+},*)$, so
$\mathcal{Q}\cup\mathcal{P}\backslash P_{1}$ is a partition of $V(G)$ with
type $(2^{+},1^{+},*)$. Now (a) gives
$w_{H}(\mathcal{Q})=w_{G}(\mathcal{Q}\cup\mathcal{P}\setminus
P_{1})-w_{G}(\mathcal{P})+19\geqslant 9-15+19=13$. So 1.8(2) gives
$H/\mathcal{Q}\notin\mathcal{N}\cup\mathcal{W}^{*}$. Thus, by definition $H$
is $\mathcal{N}$-good.

For (c), suppose $\mathcal{P}$ is a partition with type $(2^{+},2^{+},\ast)$
such that $w_{G}(\mathcal{P})\leqslant 17$ and $|\mathcal{P}|$ is maximized.
For the trivial partition $\mathcal{Q}_{0}$ of $V(H)$, the partition
$\mathcal{Q}_{0}\cup\mathcal{P}\backslash P_{1}$ of $V(G)$ has type
$(2^{+},1^{+},\ast)$, so (a) gives
$w_{H}(\mathcal{Q}_{0})=w_{G}(\mathcal{Q}_{0}\cup\mathcal{P}\backslash
P_{1})-w_{G}(\mathcal{P})+19\geqslant 9-17+19=11$. Now 1.8(1) gives
$H/\mathcal{Q}_{0}\notin\mathcal{N}$. Every nontrivial partition $\mathcal{Q}$
has type $(2^{+},1^{+},\ast)$ and $\mathcal{Q}\cup\mathcal{P}\backslash P_{1}$
has type$(2^{+},2^{+},\ast)$, as a partition of $V(G)$, with
$|\mathcal{Q}\cup\mathcal{P}\backslash P_{1}|>|\mathcal{P}|$. By the
maximality of $|\mathcal{P}|$, we have
$w_{G}(\mathcal{Q}\cup\mathcal{P}\backslash P_{1})\geqslant 18$, so
$w_{H}(\mathcal{Q})=w_{G}(\mathcal{Q}\cup\mathcal{P}\backslash
P_{1})-w_{G}(\mathcal{P})+19\geqslant 18-17+19=20$, and 1.8(2) gives
$H/\mathcal{Q}\notin\mathcal{N}\cup\mathcal{W}^{*}$. By definition, $H$ is
$\mathcal{N}$-good.

For (d), suppose $\mathcal{P}$ is a partition with type $(4^{+},1^{+},*)$ such
that $w_{G}(\mathcal{P})\leqslant 19$. We consider a partition $\mathcal{Q}$
of $V(H)$. If $\mathcal{Q}$ is trivial, then $w_{H}(\mathcal{Q})\geqslant
0-19+19=0$ and $H/\mathcal{Q}\notin\mathcal{N}$ as $|\mathcal{Q}|\geqslant 4$.
If $\mathcal{Q}$ has type $(2^{+},1^{+},*)$ and $|\mathcal{Q}|\geqslant 3$,
then $\mathcal{Q}\cup\mathcal{P}\backslash P_{1}$ (as a partition of $V(G)$)
has type $(2^{+},1^{+},*)$, so (a) gives $w_{H}(\mathcal{Q})\geqslant
9-19+19=9$. Now 1.8(4) gives
$H/\mathcal{Q}\notin\mathcal{N}\cup\mathcal{W}^{*}$. Otherwise $\mathcal{Q}$
has type either $(3^{+},1^{+},*)$ or $(2^{+},2^{+},*)$, so (b) and (c) give
$w_{H}(\mathcal{Q})\geqslant\min\\{16,18\\}-19+19=16$. So 1.8(2) gives
$H/\mathcal{Q}\notin\mathcal{N}\cup\mathcal{W}^{*}$. By definition, $H$ is
$\mathcal{N}$-good.

For (e), suppose $\mathcal{P}$ is a partition with type $(3^{+},2^{+},*)$ such
that $w_{G}(\mathcal{P})\leqslant 24$. For the trivial partition
$\mathcal{Q}_{0}$ of $V(H)$, the partition
$\mathcal{Q}_{0}\cup\mathcal{P}\backslash P_{1}$ of $V(G)$ has type
$(2^{+},1^{+},\ast)$, so (a) gives $w_{H}(\mathcal{Q}_{0})\geqslant
9-24+19=4$. As $|\mathcal{Q}_{0}|\geqslant 3$, 1.8(3) gives
$H/\mathcal{Q}_{0}\notin\mathcal{N}$. Every nontrivial partition $\mathcal{Q}$
has type $(2^{+},1^{+},*)$ so the partition
$\mathcal{Q}\cup\mathcal{P}\backslash P_{1}$ of $V(G)$ has type
$(2^{+},2^{+},*)$; thus (c) gives $w_{H}(\mathcal{Q})\geqslant 18-24+19=13$.
Now 1.8(2) gives $H/\mathcal{Q}\notin\mathcal{N}\cup\mathcal{W}^{*}$. By
definition, again $H$ is $\mathcal{N}$-good.

For (f), assume $\mathcal{P}$ is a partition with type $(3^{+},3^{+},*)$ such
that $w_{G}(\mathcal{P})\leqslant 31$. For the trivial partition
$\mathcal{Q}_{0}$, the partition $\mathcal{Q}_{0}\cup\mathcal{P}\backslash
P_{1}$ of $V(G)$ has type $(3^{+},1^{+},\ast)$, so (b) gives
$w_{H}(\mathcal{Q}_{0})\geqslant 16-31+19=4$. Since
$|\mathcal{Q}_{0}|\geqslant 3$, 1.8(3) gives
$H/\mathcal{Q}_{0}\notin\mathcal{N}$. For every partition $\mathcal{Q}$ of
type $(2^{+},1^{+},*)$, the partition $\mathcal{Q}\cup\mathcal{P}\backslash
P_{1}$ of $V(G)$ has type $(3^{+},2^{+},*)$, so (e) gives
$w_{H}(\mathcal{Q})\geqslant 25-31+19=13$. Now 1.8(2) gives
$H/\mathcal{Q}\notin\mathcal{N}\cup\mathcal{W}^{*}$. By definition, $H$ is
$\mathcal{N}$-good. ∎

Since $v(G)\geqslant 5$, Lemma 4.1 gives the following lower bound on the
edge-connectivity of $G$.

######  Lemma 4.2.

The graph $G$ is $12$-edge-connected. If $[X,X^{c}]$ is an edge-cut of $G$,
then

  1. (1)

when $|X|\geqslant 3$ and $|X^{c}|\geqslant 2$, we have $|[X,X^{c}]|\geqslant
15$;

  2. (2)

when $|X|\geqslant 3$ and $|X^{c}|\geqslant 3$, we have $|[X,X^{c}]|\geqslant
18$.

###### Proof.

Note that $\mathcal{P}=\\{X,X^{c}\\}$ is a partition of $V(G)$. Since
$v(G)\geqslant 5$, we know $\mathcal{P}$ has type either $(4^{+},1^{+})$ or
$(3^{+},2^{+})$. By Lemma 4.1(d) and (e), we have
$w_{G}(\mathcal{P})=2|[X,X^{c}]|-23\times 2+42\geqslant\min\\{20,25\\},$ which
implies $|[X,X^{c}]|\geqslant 12$; thus $G$ is $12$-edge-connected.

For (1), by Lemma 4.1(e), we have $2|[X,X^{c}]|-23\times 2+42\geqslant 25$.
Thus $|[X,X^{c}]|\geqslant\lceil 29/2\rceil=15$. For (2), by Lemma 4.1(f), we
have $2|[X,X^{c}]|-23\times 2+42\geqslant 32$. Thus $|[X,X^{c}]|\geqslant 18$.
∎

Next, we give the first configuration forbidden in the minimal counterexample
$G$.

######  Lemma 4.3.

The graph $G$ contains no $T_{1,1,7}$.

###### Proof.

Suppose to the contrary that $G$ contains $T_{1,1,7}$ as a subgraph as shown
in Figure 2(a). We lift an edge-pair ($xv,vy$) at $v$, contract the resulting
$8K_{2}$, denote by $w_{xy}$ the vertex formed from the contraction, and
denote the resulting graph by $G^{\prime}$. Note that
$v(G^{\prime})=v(G)-1\geqslant 4$ and $e(G^{\prime})=e(G)-9$. As $8K_{2}$ is
an $\mathcal{N}$-good graph, to contradict Theorem 1.11(2), it suffices to
prove that $G^{\prime}$ is $\mathcal{S}$-good.

For the trivial partition $\mathcal{P}^{\prime}_{0}$ of $V(G^{\prime})$ and
the trivial partition $\mathcal{P}_{0}$ of $V(G)$, we have
$w_{G^{\prime}}(\mathcal{P}^{\prime}_{0})=w_{G}(\mathcal{P}_{0})-2\times
9+23\times 1\geqslant w(G)-18+23=5$. Moreover,
$|\mathcal{P}^{\prime}_{0}|=v(G^{\prime})\geqslant 4$, which gives
$G^{\prime}/\mathcal{P}^{\prime}_{0}\notin\mathcal{N}\cup\mathcal{W}^{*}$. Let
$\mathcal{P}^{\prime}$ be a nontrivial partition of $V(G^{\prime})$ and
$\mathcal{P}$ be its corresponding partition of $V(G)$. For every partition
$\mathcal{P}^{\prime}$ with type $(2^{+},1^{+},\ast)$, the corresponding
partition $\mathcal{P}$ has type either $(3^{+},1^{+},\ast)$ or
$(2^{+},2^{+},\ast)$; thus Lemma 4.1(b) and (c) give
$w_{G}(\mathcal{P})\geqslant\min\\{16,18\\}=16$. Now
$w_{G^{\prime}}(\mathcal{P}^{\prime})=w_{G}(\mathcal{P})-2\times 2\geqslant
12$. Furthermore, $G^{\prime}$ is $10$-edge-connected by Lemma 4.2. So 1.8(5)
gives $G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$.
Noting that $w(G^{\prime})\geqslant 5$, we conclude that $G^{\prime}$ is
$\mathcal{S}$-good, as desired. ∎

The next lemma helps us handle vertices in $G$ of small degree.

######  Lemma 4.4.

Let $G$ contain a vertex $v$ with $d_{G}(v)\leqslant 14$. Let $G^{\prime}$ be
a graph formed from $G$ by lifting $\alpha$ edge-pairs at $v$ such that
$d_{G}(v)-\alpha\leqslant 11$ and $d_{G}(v)-2\alpha\geqslant 8$, and let
$G^{\prime\prime}=G^{\prime}-v$. If $G^{\prime\prime}$ contains no $9K_{2}$,
then $G^{\prime\prime}$ is $\mathcal{S}$-good and
$G^{\prime}/\mathcal{P}\notin\mathcal{N}$ for every partition $\mathcal{P}$ of
$V(G^{\prime})$.

###### Proof.

Note that $v(G^{\prime\prime})=v(G)-1\geqslant 4$, and
$e(G^{\prime\prime})=e(G)-(d_{G}(v)-\alpha)$. We begin with the following
claim, which implies that $G^{\prime\prime}$ is $\mathcal{S}$-good.

_Claim: $w(G^{\prime\prime})\geqslant 0$ and
$G^{\prime\prime}/\mathcal{P}^{\prime\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$
for every partition $\mathcal{P}^{\prime\prime}$ of $V(G^{\prime\prime})$._

The trivial partition $\mathcal{P}^{\prime\prime}_{0}$ of
$V(G^{\prime\prime})$ satisfies
$w_{G^{\prime\prime}}(\mathcal{P}_{0}^{\prime\prime})=w_{G}(\mathcal{P}_{0})-2\times(d_{G}(v)-\alpha)+23\times
1\geqslant w(G)-2\times 11+23\geqslant 1$, where $\mathcal{P}_{0}$ is the
trivial partition of $V(G)$. Further,
$|\mathcal{P}^{\prime\prime}_{0}|=v(G^{\prime\prime})\geqslant 4$, so
$G^{\prime\prime}/\mathcal{P}^{\prime\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$.
Let $\mathcal{P}^{\prime\prime}=\\{P_{1},P_{2},\ldots P_{t}\\}$ be a
nontrivial partition of $V(G^{\prime\prime})$. If $\mathcal{P}^{\prime\prime}$
is a partition of $V(G^{\prime\prime})$ with type $(4^{+},1^{+},*)$ or type
$(2^{+},2^{+},*)$, then $\mathcal{P}^{\prime\prime}\cup\\{v\\}$ also has type
$(4^{+},1^{+},*)$ or $(2^{+},2^{+},*)$ as a partition of $V(G)$. Then Lemma
4.1(c) and (d) imply
$w_{G^{\prime\prime}}(\mathcal{P}^{\prime\prime})\geqslant
w_{G}(\mathcal{P}^{\prime\prime}\cup\\{v\\})-2\times d_{G}(v)+23\times
1\geqslant\min\\{18,20\\}-28+23=13$. So 1.8(2) gives
$G^{\prime\prime}/\mathcal{P}^{\prime\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$.
Thus we assume $|P_{1}|\in\\{2,3\\}$ and $|P_{i}|=1$ for all $i\geqslant 2$.
First consider such a partition $\mathcal{P}^{\prime\prime}$ with type
$(2,1,*)$ and let $P_{1}=\\{x,y\\}$. Since $G^{\prime\prime}$ contains no
$9K_{2}$, we have $w_{G^{\prime\prime}}(\mathcal{P}^{\prime\prime})\geqslant
w_{G^{\prime\prime}}(\mathcal{P}^{\prime\prime}_{0})-2\times\mu_{G^{\prime\prime}}(xy)+23\times
1\geqslant 1-16+23=8$. Since $v(G^{\prime\prime})\geqslant 4$, we have
$|\mathcal{P}^{\prime\prime}|\geqslant 3$, so 1.8(4) implies
$G^{\prime\prime}/\mathcal{P}^{\prime\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$.

Instead we assume $\mathcal{P}^{\prime\prime}$ has type $(3,1,*)$. For every
type $(3,1,*)$ partition $\mathcal{P}^{\prime\prime}$ of
$V(G^{\prime\prime})$, we know that $\mathcal{P}^{\prime\prime}\cup\\{v\\}$ is
a type $(3,1,*)$ partition of $V(G)$, so Lemma 4.1(b) implies
$w_{G^{\prime\prime}}(\mathcal{P}^{\prime\prime})\geqslant
w_{G}(\mathcal{P}^{\prime\prime}\cup\\{v\\})-2\times d_{G}(v)+23\times
1\geqslant 16-28+23=11$. Thus 1.8(1) gives
$G^{\prime\prime}/\mathcal{P}^{\prime\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}\backslash\\{8K_{2}\\}$.
So we assume $G^{\prime\prime}/\mathcal{P}^{\prime\prime}=8K_{2}$ where
$\mathcal{P}^{\prime\prime}=\\{P_{1},P_{2}\\}$ with $|P_{1}|=3$ and
$|P_{2}|=1$. Moreover, this case holds only if we lifted $\alpha$ edge-pairs
at $v$ such that $\alpha$ edges have been added into $G[P_{1}]$ and
$d_{G}(v)=14$; otherwise, the inequality above can be improved to
$w_{G^{\prime\prime}}(\mathcal{P}^{\prime\prime})\geqslant 13$, and we are
done. Thus $\alpha=3$ and $v$ has at least two neighbours in $P_{1}$.

Note that $v(G)=5$ and $0\leqslant w(G)\leqslant\sum_{v\in
V(G)}d(v)-23v(G)+42=2e(G)-115+42$, so $e(G)\geqslant\lceil 73/2\rceil=37$, and
then $e(G[P_{1}])=e(G)-d_{G}(v)-e_{G}(P_{1},P_{2})\geqslant 37-14-8=15$. That
is, $G[P_{1}]$ is a multitriangle $T_{a,b,c}$ with $a+b+c\geqslant 15$. If
$a+b+c\geqslant 16$, then $\delta(G[P_{1}])\geqslant 9$ because $G$ has no
$8K_{2}$. Thus $G[P_{1}]$ is an $\mathcal{N}$-good subgraph of $G$, which
contradicts Theorem 1.11(1). So assume $a+b+c=15$. Note that
$e_{G}(P_{1},P_{2}\cup\\{v\\})\geqslant 15$ and $d_{G}(P_{2})\geqslant 12$ by
Lemma 4.2. Since $G$ contains no $T_{1,1,7}$ (by Lemma 4.3), we know
$\mu(G[P_{1}])\leqslant 6$, so $\delta(G[P_{1}])\geqslant 9$. In this case, we
lift an edge-pair at $v$ to add an edge into $G[P_{1}]$ and denote it by
$G_{1}$. It is easy to see that $G_{1}$ is a multitriangle (induced by
$P_{1}$) with $e(G_{1})\geqslant 16$ and $\delta(G_{1})\geqslant 9$, and thus
$G_{1}$ is an $\mathcal{N}$-good graph. Then we contract $G_{1}$, and note
that the graph formed by contraction is an $\mathcal{S}$-good graph on three
vertices with at least $20$ edges and minimum degree at least $9$. Hence, it
contradicts Theorem 1.11(2). Therefore,
$w_{G^{\prime\prime}}(\mathcal{P}^{\prime\prime})\geqslant 0$ and
$G^{\prime\prime}/\mathcal{P}^{\prime\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$
for every partition $\mathcal{P}^{\prime\prime}$, which proves our claim.

Next we prove that $G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}$ for
every partition $\mathcal{P}^{\prime}$ of $V(G^{\prime})$. We consider two
cases based on the size of $\mathcal{P}^{\prime}$. First suppose that
$\mathcal{P}^{\prime}$ is a partition of $V(G^{\prime})$ with two parts
$P_{1}$ and $P_{2}$. By symmetry, we assume $v\in P_{1}$. If $P_{1}=\\{v\\}$,
then $e(P_{1},P_{2})=d_{G^{\prime}}(v)\geqslant 8$, so
$G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}$. Thus, we assume
$|P_{1}|\geqslant 2$. Hence, $\\{P_{1}-v,P_{2}\\}$ is a partition of
$V(G^{\prime\prime})$. Since
$G^{\prime\prime}/\\{P_{1}-v,P_{2}\\}\notin\mathcal{N}\cup\mathcal{W}^{*}$, we
know that
$e_{G^{\prime}}(P_{1}-v,P_{2})=e_{G^{\prime\prime}}(P_{1}-v,P_{2})\geqslant
9$, and thus $e_{G^{\prime}}(P_{1},P_{2})\geqslant 9$. Hence,
$G^{\prime}/\mathcal{P}^{\prime}\notin\\{\alpha K_{2}:\alpha\leqslant 7\\}$.
Now instead we consider a partition $\mathcal{P}^{\prime}$ of $V(G^{\prime})$
with three parts $P_{1}$, $P_{2}$, and $P_{3}$. If $P_{1}=\\{v\\}$, then
$\\{P_{2},P_{3}\\}$ is a partition of $V(G^{\prime\prime})$. Since
$e_{G^{\prime}}(P_{2},P_{3})=e_{G^{\prime\prime}}(P_{2},P_{3})\geqslant 9$ and
$d_{G^{\prime}}(v)\geqslant 8$, we know
$e(G^{\prime}/\mathcal{P}^{\prime})\geqslant 9+8=17$, so
$G^{\prime}/\mathcal{P}^{\prime}\notin\\{T_{a,b,c}:a+b+c\leqslant 15\\}$. If
$v\in P_{1}$ and $|P_{1}|\geqslant 2$, then we consider a partition of
$V(G^{\prime\prime})$ with parts $P_{1}-v,P_{2},P_{3}$; call it
$\mathcal{P}^{\prime\prime}$. By the above claim,
$G^{\prime\prime}/\mathcal{P}^{\prime\prime}\notin\\{T_{a,b,c}:a+b+c\leqslant
15\\}$; thus $G^{\prime}/\mathcal{P}^{\prime}\notin\\{T_{a,b,c}:a+b+c\leqslant
15\\}$. Therefore, there is no partition $\mathcal{P}^{\prime}$ of
$V(G^{\prime})$ such that $G^{\prime}/\mathcal{P}^{\prime}\in\mathcal{N}$. ∎

The next result is the first application of the above lemma. In fact, we show
that $\delta(G)\geqslant 14$.

######  Lemma 4.5.

The graph $G$ is $14$-edge-connected.

###### Proof.

It suffices to prove that $\delta(G)\geqslant 14$. The lemma then follows from
the fact that $v(G)\geqslant 5$, as if $[X,X^{c}]$ is an edge-cut with
$|X|\geqslant 2$ and $|X^{c}|\geqslant 3$, then Lemma 4.2(1) gives
$|[X,X^{c}]|\geqslant 15$.

Suppose to the contrary that $\delta(G)\leqslant 13$. By Lemma 4.2, we have
$\delta(G)\in\\{12,13\\}$. Let $v$ be a vertex of $G$ with
$d_{G}(v)=\delta(G)$. We lift two edge-pairs at $v$ to form a new graph
$G^{\prime}$, delete the vertex $v$, and denote the resulting graph by
$G^{\prime\prime}$. Note that $d_{G}(v)-2\in\\{10,11\\}$ and $d_{G}(v)-2\times
2\in\\{8,9\\}$. Since $G$ contains no $8K_{2}$ and $G$ contains no $T_{1,1,7}$
(by Lemma 4.3), we know that $\mu_{G^{\prime\prime}}(xy)\leqslant 8$ for every
two vertices $x,y\in V(G^{\prime\prime})$. Thus, by Lemma 4.4,
$G^{\prime\prime}$ is $\mathcal{S}$-good and
$G^{\prime}/\mathcal{P}\notin\mathcal{N}$ for every partition $\mathcal{P}$ of
$V(G^{\prime})$, contradicting Theorem 1.11(3). ∎

After improving our bounds on the edge-connectivity of $G$, we can lift more
edge-pairs in $G$. We make this more precise in the next lemma.

######  Lemma 4.6.

Let $G_{1}$ be a graph formed from $G$ by lifting $X$ edge-pairs, $Y$ edge-
triples, and $Z$ edge-quadruples with $X+Y+Z\leqslant 2$. If also
$X+2Y+3Z\leqslant 3$, then $G_{1}$ contains no $8K_{2}$.

###### Proof.

Recall that $G$ has no $T_{1,1,7}$ by Lemma 4.3; since at most $X+Y+Z\leqslant
2$ new edges may be created by lifting, $G_{1}$ has no $9K_{2}$. Suppose the
lemma is false; that is, $G_{1}$ contains $8K_{2}$. We contract $8K_{2}$ and
denote the resulting graph by $G^{\prime}$. Since $X+2Y+3Z\leqslant 3$, after
lifting and contracting, $v(G^{\prime})=v(G)-1\geqslant 4$ and
$e(G^{\prime})\geqslant e(G)-(8+X+2Y+3Z)\geqslant e(G)-11$. By Lemma 4.5,
$G_{1}$ has edge-connectivity at least $14-(2X+3Y+4Z)\geqslant 14-(2+3)=9$ and
thus $G^{\prime}$ is also $9$-edge-connected.

For the trivial partition $\mathcal{P}_{0}^{\prime}$ of $V(G^{\prime})$, we
have $w_{G^{\prime}}(\mathcal{P}_{0}^{\prime})\geqslant w(G)-2\times
11+23\times 1\geqslant 1$. Because $|\mathcal{P}_{0}^{\prime}|\geqslant 4$,
clearly
$G^{\prime}/\mathcal{P}_{0}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$. Let
$\mathcal{P}^{\prime}$ be a nontrivial partition of $V(G^{\prime})$ and
$\mathcal{P}$ be the corresponding partition of $V(G)$. If
$\mathcal{P}^{\prime}$ has type $(2^{+},1^{+},\ast)$, then $\mathcal{P}$ is a
partition of $V(G)$ with type either $(3^{+},1^{+},\ast)$ or
$(2^{+},2^{+},\ast)$. Hence, Lemma 4.1(b) and (c) give
$w_{G}(\mathcal{P})\geqslant\min\\{16,18\\}=16$. Let $m$ denote the number of
edges that are counted in $\omega_{G}(\mathcal{P})$ but not in
$\omega_{G^{\prime}}(\mathcal{P}^{\prime})$. Note that $m\leqslant
2X+3Y+4Z\leqslant 5$. Thus, $w_{G^{\prime}}(\mathcal{P}^{\prime})\geqslant
w_{G}(\mathcal{P})-2\times m\geqslant 16-2m\geqslant 6$. Because $G^{\prime}$
is $9$-edge-connected, 1.8(5) gives
$G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$. Since
$w(G^{\prime})\geqslant 1$, $G^{\prime}$ is an $\mathcal{S}$-good graph,
contradicting Theorem 1.11(2). ∎

$x$$y$$v$ (a) $T_{1,1,7}$

$u$$v$$x$$y$ (b) $Q_{1,1,1,7}$

$u$$v$$w$$x$$y$ (c) $V_{1,1,1,1,7}$

$u$$x$$y$ (d) $T_{2,2,6}$

$u$$v$$x$$y$ (e) $T^{o}_{1,1,7}$

$u$$v$$x$$y$$w$ (f) $Q^{o}_{1,1,1,7}$

Figure 2: Some forbidden configurations in $G$: (a) for Lemma 4.3, and (b)-(f)
for Lemma 4.7

######  Lemma 4.7.

$G$ contains none of $Q_{1,1,1,7}$, $V_{1,1,1,1,7}$, $T_{2,2,6}$,
$T_{1,1,7}^{o}$, and $Q_{1,1,1,7}^{o}$.

###### Proof.

If $G$ contains one of these 5 configurations, shown in Figure 2(b)–2(f), then
we lift some edge-pair, edge-triple, edge-quadruple, or combination of these
as allowed in Lemma 4.6. We lift at most $5$ edges, so the resulting graph
$G_{1}$ satisfies the hypotheses of Lemma 4.6; namely, $X+Y+Z\leqslant 2$ and
$X+2Y+3Z\leqslant 3$. However, we have $\mu_{G_{1}}(xy)=8$. This contradicts
Lemma 4.6, which implies the result. ∎

######  Lemma 4.8.

$G$ contains no $T^{o}_{2,2,6}$.

###### Proof.

Suppose $G$ has a copy of $T^{o}_{2,2,6}$ as shown in Figure 3(a). We lift an
edge-pair $(xv,vy)$ at $v$ and two edge-pairs $(xu,uy)$ at $u$, contract the
resulting $8K_{2}$ into a new vertex $w_{xy}$, and denote the resulting graph
by $G^{\prime}$.

First we show that $G^{\prime}$ is $9$-edge-connected. By Lemma 4.5,
$d_{G^{\prime}}(u)=d_{G}(u)-4\geqslant 14-4=10$ and
$d_{G^{\prime}}(v)=d_{G}(v)-2\geqslant 12$. Since $G$ contains no $T_{2,2,6}$
by Lemma 4.7, $\mu_{G}(xy)=5$. Thus,
$d_{G^{\prime}}(w_{xy})=d_{G}(x)+d_{G}(y)-2\times\mu_{G}(xy)-6\geqslant
14+14-2\times 5-6=12$. Moreover, $d_{G^{\prime}}(z)=d_{G}(z)\geqslant 14$ for
every vertex $z\in V(G^{\prime})\setminus\\{u,v,w_{xy}\\}$. If $[X,X^{c}]$ is
an edge-cut of $G^{\prime}$ with $|X|\geqslant 2$ and $|X^{c}|\geqslant 2$,
then lemma 4.2(1) gives $|[X,X^{c}]|\geqslant 15-6=9$. Therefore, $G^{\prime}$
is $9$-edge-connected.

Now we show that $G^{\prime}$ is $\mathcal{S}$-good. Note that
$v(G^{\prime})=v(G)-1$ and $e(G^{\prime})=e(G)-11$. For the trivial partition
$\mathcal{P}^{\prime}_{0}$ of $V(G^{\prime})$,
$w_{G^{\prime}}(\mathcal{P}^{\prime}_{0})\geqslant w(G)-2\times 11+23\times
1=1$. Since $|\mathcal{P}^{\prime}_{0}|=v(G^{\prime})\geqslant 4$,
$G^{\prime}/\mathcal{P}_{0}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$.
Next, we consider the values of $w_{G^{\prime}}(\mathcal{P}^{\prime})$ for
every nontrivial partition $\mathcal{P}^{\prime}$. Let $\mathcal{P}$ be the
partition of $V(G)$ corresponding to $\mathcal{P}^{\prime}$. We consider the
following two cases.

Case 1: at least one of $\bm{u}$ and $\bm{v}$ is in the same part as
$\bm{w_{xy}}$. Note that $\mathcal{P}$ is type $(3^{+},1^{+},\ast)$. So Lemma
4.1(b) gives $w_{G^{\prime}}(\mathcal{P}^{\prime})\geqslant
w_{G}(\mathcal{P})-2\times 4\geqslant 16-8=8$. Since $G^{\prime}$ is $9$-edge-
connected, 1.8(5) implies
$G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$.

Case 2: $\bm{u}$, $\bm{v}$, and $\bm{w_{xy}}$ are in three different parts of
$\bm{\mathcal{P}^{\prime}}$. Now none of the 6 edges in the multiset
$\\{xu,xu,uy,uy,xv,vy\\}$ are counted in
$\omega_{G^{\prime}}(\mathcal{P}^{\prime})$. If $\mathcal{P}^{\prime}$ has
type $(3^{+},1^{+},\ast)$ or type $(2^{+},2^{+},\ast)$, then $\mathcal{P}$ has
either type $(4^{+},1^{+},\ast)$ or type $(3^{+},2^{+},\ast)$. So Lemma 4.1(d)
and (e) imply $w_{G^{\prime}}(\mathcal{P}^{\prime})\geqslant
w_{G}(\mathcal{P})-2\times 6\geqslant\min\\{20,25\\}-12=8$. Since $G^{\prime}$
is $9$-edge-connected, 1.8(5) implies
$G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$. Assume
instead that $\mathcal{P}^{\prime}$ is type $(2,1,\ast)$, so
$|\mathcal{P}^{\prime}|\geqslant 3$. Now $\mathcal{P}$ is either type
$(3,1,\ast)$ or type $(2,2,\ast)$. Furthermore, Lemma 4.1(b) and (c) give
$w_{G^{\prime}}(\mathcal{P}^{\prime})\geqslant w_{G}(\mathcal{P})-2\times
6\geqslant\min\\{16,18\\}-12=4$. Thus, 1.8(3) implies
$G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}\backslash\\{T_{a,b,c}:a+b+c=16\\}$.
Note that
$G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$ unless
$\mathcal{P}^{\prime}$ is type $(2,1,\ast)$ with $|\mathcal{P}^{\prime}|=3$
and $G^{\prime}/\mathcal{P}^{\prime}\in\\{T_{a,b,c}:a+b+c=16\\}$. We now
handle this exceptional case.

Since $\mathcal{P}^{\prime}$ has type $(2,1,\ast)$ with
$|\mathcal{P}^{\prime}|=3$, we have $v(G^{\prime})=4$ and $v(G)=5$. Let $z$ be
the vertex in $V(G^{\prime})$ that is distinct from $v$, $u$, and $w_{xy}$.
Recall that $w(G)\geqslant 0$, so $e(G)\geqslant\lceil 73/2\rceil=37$. By
Lemma 4.7, $G$ contains no $T_{2,2,6}$, so $\mu_{G}(xy)=5$. We consider
different kinds of partitions of $V(G)$ based on which part contains the
vertex $z$. If $\mathcal{P}^{\prime}=\\{\\{w_{xy}\\},\\{u,z\\},\\{v\\}\\}$,
then $\mathcal{P}=\\{\\{x,y\\},\\{u,z\\},\\{v\\}\\}$. This gives
$\mu_{G}(uz)=e(G)-e(T^{o}_{2,2,6})-e(G^{\prime}/\mathcal{P}^{\prime})\geqslant
37-11-16=10$. Hence, $G$ contains an $\mathcal{N}$-good subgraph $\alpha
K_{2}$ with $\alpha\geqslant 10$, contradicting Theorem 1.11(1). Similarly, if
$\mathcal{P}^{\prime}=\\{\\{w_{xy}\\},\\{u\\},\\{v,z\\}\\}$, then
$\mu_{G}(vz)\geqslant 10$, a contradiction. So we assume instead that $z$ is
in the same part as $w_{xy}$. That is,
$\mathcal{P}^{\prime}=\\{\\{w_{xy},z\\},\\{u\\},\\{v\\}\\}$, so
$\mathcal{P}=\\{\\{x,y,z\\},\\{u\\},\\{v\\}\\}$. Now a short argument on the
edges incident to $u$ will give a contradiction. In the second paragraph of
this proof, we showed $d_{G^{\prime}}(u)\geqslant 10$ and
$d_{G^{\prime}}(v)\geqslant 12$. Because
$e(G^{\prime}/\mathcal{P}^{\prime})=16$, we get
$e_{G^{\prime}}(P_{1},P_{2})=16-d_{G^{\prime}}(v)\leqslant 4$. Since $G$
contains no $T^{o}_{1,1,7}$, we also get
$e_{G^{\prime}}(P_{2},P_{3})=\mu_{G}(uv)\leqslant 5$. As $P_{2}=\\{u\\}$,
together these give
$d_{G^{\prime}}(u)=e_{G^{\prime}}(P_{1},P_{2})+e_{G^{\prime}}(P_{2},P_{3})\leqslant
4+5=9$, a contradiction. Therefore,
$G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$ for
every partition $\mathcal{P}^{\prime}$ of $V(G^{\prime})$.

In each case, $G^{\prime}$ is $\mathcal{S}$-good, contradicting Theorem
1.11(2). ∎

$u$$v$$x$$y$ (a) $T^{o}_{2,2,6}$

$v$$y$$x$ (b) $T_{3,3,5}$

Figure 3: The graphs $T^{o}_{2,2,6}$ in Lemma 4.8 and $T_{3,3,5}$ in Lemma 4.9

To prove our next result, we again use Lemma 4.4 to handle vertices in $G$ of
small degree.

######  Lemma 4.9.

$G$ contains no $T_{3,3,5}$.

###### Proof.

Suppose $G$ contains $T_{3,3,5}$ as a subgraph as shown in Figure 3(b). We
lift three edge-pairs $(xv,vy)$ at $v$, contract the resulting $8K_{2}$,
denote by $w_{xy}$ the new vertex formed by contraction, and denote the
resulting graph by $G^{\prime}$. Note that $v(G^{\prime})=v(G)-1\geqslant 4$
and $e(G^{\prime})=e(G)-11$. For the trivial partition
$\mathcal{P}^{\prime}_{0}$ of $V(G^{\prime})$, we have
$w_{G^{\prime}}(\mathcal{P}^{\prime}_{0})\geqslant w(G)-2\times 11+23=1$.
Hence,
$G^{\prime}/\mathcal{P}^{\prime}_{0}\notin\mathcal{N}\cup\mathcal{W}^{*}$
since $|\mathcal{P}^{\prime}_{0}|\geqslant 4$. Let $\mathcal{P}^{\prime}$ be a
nontrivial partition of $V(G^{\prime})$ and $\mathcal{P}$ be the corresponding
partition of $V(G)$. If $w_{xy}$ and $v$ are in the same part of
$\mathcal{P}^{\prime}$, then $\mathcal{P}$ has type $(3^{+},1^{+},\ast)$; thus
Lemma 4.1(b) implies
$w_{G^{\prime}}(\mathcal{P}^{\prime})=w_{G}(\mathcal{P})\geqslant 16$, so
1.8(2) gives
$G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$. From
now on, we assume that $w_{xy}$ and $v$ are in different parts of
$\mathcal{P}^{\prime}$. We consider the following two types of partitions.

Case 1: $\bm{\mathcal{P}^{\prime}}$ has type $\bm{(2,1,\ast)}$. Now
$|\mathcal{P}^{\prime}|\geqslant 3$ since $v(G^{\prime})\geqslant 4$; so Lemma
4.1(b) and (c) give $w_{G^{\prime}}(\mathcal{P}^{\prime})\geqslant
w_{G}(\mathcal{P})-2\times 6\geqslant\min\\{16,18\\}-12=4$. Thus
$G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}\backslash\\{T_{a,b,c}:a+b+c=16\\}$.
Suppose $\mathcal{P}^{\prime}=\\{P_{1},P_{2},P_{3}\\}$ with $|P_{1}|=2$ and
$|P_{2}|=|P_{3}|=1$, and
$G^{\prime}/\mathcal{P}^{\prime}=\\{T_{a,b,c}:a+b+c=16\\}$. Denote
$V(G^{\prime})$ by $\\{w_{xy},v,v_{1},v_{2}\\}$. Note that $v(G)=5$ and
$0\leqslant w(G)\leqslant 2e(G)-5\times 23+42$ gives $e(G)\geqslant\lceil
73/2\rceil=37$. If
$\mathcal{P}^{\prime}=\\{\\{w_{xy}\\},\\{v,v_{1}\\},\\{v_{2}\\}\\}$, then
$\mu_{G}(v_{1}v)=e(G)-e(G^{\prime}/\mathcal{P}^{\prime})-e(T_{3,3,5})\geqslant
37-16-11=10$. So $G$ has an $\mathcal{N}$-good subgraph $\alpha K_{2}$ with
$\alpha\geqslant 10$, contradicting Theorem 1.11(1). Similarly, in the case
$\mathcal{P}^{\prime}=\\{\\{w_{xy}\\},\\{v\\},\\{v_{1},v_{2}\\}\\}$ we get
$\mu_{G}(v_{1}v_{2})\geqslant 10$, a contradiction. In the remaining case
$\mathcal{P}^{\prime}=\\{\\{w_{xy},v_{1}\\},\\{v\\},\\{v_{2}\\}\\}$. Now
$\mu_{G}(v_{1}x)+\mu_{G}(v_{1}y)=e(G)-e(G^{\prime}/\mathcal{P}^{\prime})-e(T_{3,3,5})\geqslant
10$. Noting that $\mu_{G}(vx)\geqslant 3$ and $\mu_{G}(vy)\geqslant 3$, since
$G$ contains no $T^{o}_{2,2,6}$, the vertex $v_{1}$ cannot be adjacent to both
$x$ and $y$; that is, either $\mu_{G}(v_{1}x)=0$ or $\mu_{G}(v_{1}y)=0$. Thus
$G$ again contains an $\mathcal{N}$-good subgraph $\alpha K_{2}$ with
$\alpha\geqslant 10$ of $G$, again contradicting Theorem 1.11(1).

Case 2: $\mathcal{P}^{\prime}$ has type $\bm{({3^{+}},{1^{+}},*)}$ or type
$\bm{({2^{+}},{2^{+}},*)}$. Now $\mathcal{P}$ has either type
$(4^{+},1^{+},\ast)$ or type $(3^{+},2^{+},\ast)$. So Lemma 4.1(d) and (e)
imply $w_{G^{\prime}}(\mathcal{P}^{\prime})\geqslant
w_{G}(\mathcal{P})-2\times 6\geqslant\min\\{20,25\\}-12=8$. We now bound the
edge-connectivity of $G^{\prime}$. By Lemma 4.5,
$d_{G^{\prime}}(v)=d_{G}(v)-6\geqslant 14-6=8$. Since $G$ contains no
$T_{2,2,6}$, we know $\mu_{G}(xy)=5$; hence,
$d_{G^{\prime}}(w_{xy})=d_{G}(x)+d_{G}(y)-2\times\mu_{G}(xy)-6\geqslant
14+14-2\times 5-6=12$. And $d_{G^{\prime}}(u)=d_{G}(u)\geqslant 14$ for every
vertex $u\in V(G^{\prime})\backslash\\{v,w_{xy}\\}$. If $[X,X^{c}]$ is an
edge-cut of $G^{\prime}$ with $|X|\geqslant 2$ and $|X^{c}|\geqslant 2$, then
Lemma 4.2(1) implies $d_{G^{\prime}}(X)\geqslant d_{G}(X)-6\geqslant 15-6=9$.
Thus $d_{G^{\prime}}(X)\geqslant 9$ unless
$\\{X,X^{c}\\}=\\{\\{v\\},V(G^{\prime})\backslash\\{v\\}\\}$. So 1.8(5) gives
$G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}\backslash\\{8K_{2}\\}$
and $G^{\prime}/\mathcal{P}^{\prime}=8K_{2}$ only if
$\mathcal{P}^{\prime}=\\{\\{v\\},V(G^{\prime})\setminus\\{v\\}\\}$. In this
exceptional case, $d_{G}(v)=14$. Now we instead lift three edge-pairs
$(xv,vy)$ to obtain a new graph $G_{1}$, delete vertex $v$, and denote the
resulting graph by $G_{2}$. Note that $\mu_{G_{2}}(u_{1}u_{2})\leqslant 8$ for
every two vertices $u_{1},u_{2}\in V(G_{2})$, i.e., $G_{2}$ contains no
$9K_{2}$. By Lemma 4.4, $G_{2}$ is $\mathcal{S}$-good and
$G_{1}/\mathcal{P}\notin\mathcal{N}$ for every partition $\mathcal{P}$ of
$V(G_{1})$. This contradicts Theorem 1.11(3).

Therefore, $w(G^{\prime})\geqslant 1$ and
$G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$ for
every partition $\mathcal{P}^{\prime}$ of $V(G^{\prime})$. So $G^{\prime}$ is
$\mathcal{S}$-good, contradicting Theorem 1.11(2). ∎

$x$$y$$v$$u$$v_{1}$$v_{2}$ (a) $Q^{o}_{6,6,6,7}$

$z$$x$$y$$u$$v$ (b) $Q_{6,6,6,7}^{oo}$

$v_{1}$$v_{2}$$v_{3}$$x$$y$$z$ (c) $F$

Figure 4: The graphs $Q_{6,6,6,7}^{o}$ and $Q_{6,6,6,7}^{oo}$ in Lemma 4.10,
and $F$ in Lemma 4.11

######  Lemma 4.10.

$G$ contains neither $Q^{o}_{6,6,6,7}$ nor $Q^{oo}_{6,6,6,7}$.

###### Proof.

Suppose to the contrary that $G$ contains $Q^{o}_{6,6,6,7}$ or
$Q^{oo}_{6,6,6,7}$ as shown in Figure 4(a) or 4(b). The proofs for the two
configurations are quite similar. We lift some edges in $G$ to form the
subgraph $6C_{4}^{+}$, which is $\mathcal{N}$-good, contract this
$6C_{4}^{+}$, and verify that the resulting graph is $\mathcal{S}$-good. This
contradicts Theorem 1.11(2). Here we only give the proof for
$Q^{oo}_{6,6,6,7}$.

We lift two edge-pairs $(xz,zy)$ at vertex $z$, then contract the resulting
$6C_{4}^{+}$ into a new vertex $w_{xyvu}$, and denote the resulting graph by
$G^{\prime}$. Note that $v(G^{\prime})=v(G)-3\geqslant 2$. And
$\mu(xv)=\mu(uy)=0$, since otherwise $G$ contains $T^{o}_{2,2,6}$,
contradicting Lemma 4.8. Hence, $e(G^{\prime})=e(G)-27$. Furthermore, as we
only lifted 4 edges, Lemma 4.5 implies that $G^{\prime}$ has edge-connectivity
at least $14-4=10$.

For the trivial partition $\mathcal{P}^{\prime}_{0}$ of $V(G^{\prime})$, we
have $w_{G^{\prime}}(\mathcal{P}^{\prime}_{0})\geqslant w(G)-2\times
27+23\times 3\geqslant 15$ so 1.8(2) implies
$G^{\prime}/\mathcal{P}^{\prime}_{0}\notin\mathcal{N}\cup\mathcal{W}^{*}$. Let
$\mathcal{P}^{\prime}$ be a type $(2^{+},1^{+},\ast)$ partition of
$V(G^{\prime})$ and $\mathcal{P}$ be the corresponding partition of $V(G)$.
Note that $\mathcal{P}$ has type either $(5^{+},1^{+},\ast)$ or
$(4^{+},2^{+},\ast)$; by Lemma 4.1(d) we get $w_{G}(\mathcal{P})\geqslant 20$.
Thus, $w_{G^{\prime}}(\mathcal{P}^{\prime})\geqslant
w_{G}(\mathcal{P})-2\times 4\geqslant 12$. Since $G^{\prime}$ is $10$-edge-
connected, 1.8(5) gives
$G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$. In
summary, $w(G^{\prime})\geqslant 12$; so $G^{\prime}$ is $\mathcal{S}$-good,
contradicting Theorem 1.11(2). ∎

######  Lemma 4.11.

$G$ contains no copy of $F$.

###### Proof.

Suppose to the contrary that $G$ contains a subgraph $F$ on six vertices, as
shown in Figure 4(c). Note that in $F$, all three $v_{i}$’s are distinct and
thus $v(G)\geqslant 6$. We lift an edge-pair $(xv_{1},v_{1}z)$, two edge-pairs
$(xv_{2},v_{2}y)$, and an edge-pair $(yv_{3},v_{3}z)$, to form the subgraph
$T_{5,5,6}$ which is $\mathcal{N}$-good (by 1.10). Next, we contract
$T_{5,5,6}$ into a new vertex $w_{xyz}$ and denote the resulting graph by
$G^{\prime}$. Note that $v(G^{\prime})\geqslant 4$ and
$e(G^{\prime})=e(G)-20$. Lemma 4.5 gives $d_{G^{\prime}}(v)\geqslant
d_{G}(v)-4\geqslant 10$ for every $v\in V(G^{\prime})\setminus\\{w_{xyz}\\}$
and Lemma 4.2(2) implies that $d_{G^{\prime}}(w_{xyz})\geqslant 18-8=10$. Now
consider an edge cut $[X^{\prime},X^{\prime c}]$ of $G^{\prime}$ with
$|X^{\prime}|\geqslant 2$ and $|X^{\prime c}|\geqslant 2$. By symmetry, we
assume $w_{xyz}\in X^{\prime}$. If $v_{1},v_{2},v_{3}\in X^{\prime c}$, then
for the corresponding edge-cut $[X,X^{c}]$ in $G$ we have $|X|\geqslant 3$ and
$|X^{c}|\geqslant 3$, so Lemma 4.2(2) gives
$e_{G^{\prime}}(X^{\prime},X^{\prime c})\geqslant e_{G}(X,X^{c})-8\geqslant
18-8=10$. Otherwise, at most 6 of the edges that we lifted are counted in
$e_{G}(X,X^{c})$ but not in $e_{G^{\prime}}(X^{\prime},X^{\prime c})$, so
Lemma 4.2(1) gives $e_{G^{\prime}}(X^{\prime},X^{\prime c})\geqslant
e_{G}(X,X^{c})-6\geqslant 15-6=9$. Thus $G^{\prime}$ is $9$-edge-connected.

For the trivial partition $\mathcal{P}_{0}^{\prime}$ of $V(G^{\prime})$, we
have $w_{G^{\prime}}(\mathcal{P}_{0}^{\prime})\geqslant w(G)-2\times
20+23\times 2\geqslant 6$. Since
$|\mathcal{P}^{\prime}_{0}|=v(G^{\prime})\geqslant 4$, clearly
$G^{\prime}/\mathcal{P}^{\prime}_{0}\notin\mathcal{N}\cup\mathcal{W}^{*}$.
Given a type $(2^{+},1^{+},\ast)$ partition $\mathcal{P}^{\prime}$ of
$V(G^{\prime})$, denote the corresponding partition of $V(G)$ by
$\mathcal{P}$. If at least one $v_{i}$ is in the same part of
$\mathcal{P}^{\prime}$ as $w_{xyz}$, then $\mathcal{P}$ has type
$(4^{+},1^{+},\ast)$, so Lemma 4.1(d) gives
$w_{G^{\prime}}(\mathcal{P}^{\prime})\geqslant
w_{G}(\mathcal{P})-2\times\max\\{4,6\\}\geqslant 20-12=8$. If two $v_{i}$’s
are in the same part of $\mathcal{P}^{\prime}$, different from the part of
$w_{xyz}$, then $\mathcal{P}$ has type $(3^{+},2^{+},\ast)$, so Lemma 4.1(e)
gives $w_{G^{\prime}}(\mathcal{P}^{\prime})\geqslant
w_{G}(\mathcal{P})-2\times 8\geqslant 25-16=9$. In both cases, as $G^{\prime}$
is $9$-edge-connected, 1.8(5) gives
$G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$. Assume
instead that $v_{1}$, $v_{2}$, $v_{3}$, and $w_{xyz}$ are in four different
parts of $\mathcal{P}^{\prime}$. Only the 8 lifted edges between
$\\{v_{1},v_{2},v_{3}\\}$ and $\\{x,y,z\\}$ are counted in
$w_{G}(\mathcal{P})$ but not in $w_{G^{\prime}}(\mathcal{P}^{\prime})$. Hence,
$w_{G^{\prime}}(\mathcal{P}^{\prime})\geqslant w_{G}(\mathcal{P})-2\times
8\geqslant 20-16=4$. But in this case, $|\mathcal{P}^{\prime}|\geqslant 4$;
thus $G^{\prime}/\mathcal{P}^{\prime}\notin\mathcal{N}\cup\mathcal{W}^{*}$.

Altogether, $w(G^{\prime})\geqslant 4$. Hence, $G^{\prime}$ is
$\mathcal{S}$-good, contradicting Theorem 1.11(2). ∎

The proof of our final lemma relies on the fact that $G$ is planar.

######  Lemma 4.12.

Assume that $G$ contains a face $f$ that is the inner face of $T_{4,4,4}$. If
$f$ is weakly adjacent to three $3$-faces $f_{1},f_{2}$, and $f_{3}$, then for
all distinct $i,j\in[3]$, faces $f_{i}$ and $f_{j}$ cannot be weakly adjacent.

###### Proof.

Assume to the contrary, without loss of generality, that $f_{1}$ and $f_{2}$
are weakly adjacent. Let $V(T_{4,4,4})=\\{x,y,z\\}$ and let $w$ be the vertex
such that $f_{1}$ and $f_{2}$ are weakly adjacent across the multiedge $xw$.
Thus there is a multi-$K_{4}$ induced on $x,y,z,w$. We fix the planar
embedding such that $x$ is the interior vertex and $f_{1},f_{2}$, and $f$ are
three facial $3$-cycles containing $x$. Since $G$ contains no $T_{3,3,5}$ (by
Lemma 4.9), $\mu_{G}(xy)=\mu_{G}(yz)=\mu_{G}(xz)=4$. Since $G$ contains no
$T^{o}_{1,1,7}$ (by Lemma 4.7), we have $\mu_{G}(xw)\leqslant 5$. We note that
$x$ is the interior vertex, so by planarity $N_{G}(x)=\\{w,y,z\\}$. By Lemma
4.5, $d_{G}(x)\geqslant\delta(G)\geqslant 14$. However,
$d_{G}(x)=\mu_{G}(xw)+\mu_{G}(xy)+\mu_{G}(xz)\leqslant 5+4+4=13$, a
contradiction. ∎

###  4.2 Discharging part

By all the previous lemmas, $G$ contains no configuration in the set

$\\{8K_{2},T_{1,1,7},T_{2,2,6},T_{3,3,5},T_{1,1,7}^{o},T_{2,2,6}^{o},Q_{1,1,1,7},Q_{1,1,1,7}^{o},Q_{6,6,6,7}^{o},Q_{6,6,6,7}^{oo},V_{1,1,1,1,7},F\\}.$

Note that our minimal counterexample $G$ satisfies $\omega(G)\geqslant 0$, so
$2e(G)\geqslant 23v(G)-42$. Using this to substitute for $v(G)$ in Euler’s
formula that $v(G)+f(G)-e(G)=2$, we get

$\sum\limits_{f\in F(G)}d(f)=2e(G)\leqslant(2+\frac{4}{21})f(G)-\frac{8}{21}.$
(3)

We assign to each face $f$ an initial charge $d(f)$; thus the total initial
charge is strictly smaller than $\frac{46}{21}f(G)$. We then apply the
following discharging rules to redistribute the charges among the faces.

Rule (A). _Each $3^{+}$-face gives charge $\frac{2}{21}$ to each of its weakly
adjacent $2$-faces._

Rule (B). _Every inner $4$-face of $Q_{a,b,c,d}$ with $a+b+c+d\leqslant 22$
gives charge $\frac{1}{21}$ to each of its weakly adjacent $3$-faces._ _Every
inner $3$-face of $T_{a,b,c}$ with $a+b+c\leqslant 11$ gives charge
$\frac{1}{42}$ to each of its weakly adjacent $3$-faces across each edge with
multiplicity at least $4$._

Rule (C). _Each $5^{+}$-face gives charge $\frac{9}{105}$ to each of its
weakly adjacent $3$-faces and $4$-faces._

We now prove that after discharging each face ends with charge at least
$\frac{46}{21}$, which is a contradiction.

By Rule (A), every 2-face $f$ receives $\frac{2}{21}$ from each of its two
weakly adjacent $3^{+}$-faces; thus $f$ ends with at least
$2+2\times\frac{2}{21}=2+\frac{4}{21}$.

We first consider a $6^{+}$-face $f$. Since $G$ contains no $8K_{2}$, $f$ has
at most $6d(f)$ weakly adjacent $2$-faces. Moreover, since $G$ contains no
$T_{1,1,7}$ and no $Q_{1,1,1,7}$, $f$ sends charge in total at most
$d(f)\times\max\\{6\times\frac{2}{21},5\times\frac{2}{21}+\frac{9}{105}\\}=\frac{12}{21}d(f)$
to its weakly adjacent $2$-faces, $3$-faces, and $4$-faces by Rules (A) and
(C). Thus $f$ ends with at least
$d(f)-\frac{12}{21}d(f)=\frac{9}{21}d(f)>\frac{46}{21}$.

Next, we consider an inner $5$-face $f$ of the subgraph $V_{a,b,c,d,e}$ (a
multi-$C_{5}$). Note that $V_{a,b,c,d,e}$ with $a+b+c+d+e\geqslant 31$ must
contain $7K_{2}$ as a subgraph, and hence contain $V_{1,1,1,1,7}$,
contradicting Lemma 4.7. Thus $a+b+c+d+e\leqslant 30$. By Rules (A) and (C),
the face $f$ ends with at least
$5-25\times\frac{2}{21}-5\times\frac{9}{105}=\frac{46}{21}$.

Next, we consider an inner $4$-face $f$ of the subgraph $Q_{a,b,c,d}$. Since
$G$ contains no $Q_{1,1,1,7}$, $a+b+c+d\leqslant 4\times 6=24$ and
$\mu\leqslant 6$. Moreover, since $G$ contains no $Q^{o}_{1,1,1,7}$, $f$
cannot be weakly adjacent to any $3$-face across an edge with multiplicity
$6$. We consider the cases based on the value of $a+b+c+d$. Recall that Rule
(B) applies only if $a+b+c+d\leqslant 22$.

  * •

If $a+b+c+d\leqslant 21$, then by Rules (A) and (B), $f$ ends with a charge of
at least
$4-(a+b+c+d-4)\times\frac{2}{21}-4\times\frac{1}{21}=\frac{88-2(a+b+c+d)}{21}\geqslant\frac{46}{21}$.

  * •

If $a+b+c+d=22$, then we only need to consider $Q_{5,5,6,6}$, $Q_{5,6,5,6}$,
and $Q_{4,6,6,6}$. Note that if $f$ is of $Q_{5,5,6,6}$ or $Q_{5,6,5,6}$, then
$f$ is weakly adjacent to at most two $3$-faces; and if $f$ is of
$Q_{4,6,6,6}$, then $f$ is weakly adjacent to at most one $3$-face. By Rules
(A) and (B), then $f$ ends with at least
$4-18\times\frac{2}{21}-\max\\{1,2\\}\times\frac{1}{21}=\frac{46}{21}$.

  * •

If $a+b+c+d=23$, then the $4$-face $f$ must be the inner face of
$Q_{5,6,6,6}$, and by Rule (A), $f$ ends with at least
$4-19\times\frac{2}{21}=\frac{46}{21}$.

  * •

If $a+b+c+d=24$, then we just need to consider $Q_{6,6,6,6}$. Because $G$
contains no $Q_{1,1,1,7}^{o}$ and no $Q_{6,6,6,7}^{o}$, the $4$-face $f$ of
$Q_{6,6,6,6}$ must be weakly adjacent to four $5^{+}$-faces. By Rules (A) and
(C), the face $f$ (of $Q_{6,6,6,6}$) ends with at least
$4-20\times\frac{2}{21}+4\times\frac{9}{105}=\frac{256}{105}>\frac{46}{21}$.

Finally, we consider an inner $3$-face $f$ of the subgraph $T_{a,b,c}$. Since
$G$ contains no $T_{1,1,7}$, $T_{2,2,6}$, and $T_{3,3,5}$,
$a+b+c\leqslant\max\\{1+6+6,2+5+5,4+4+4\\}=13$ and $\mu\leqslant 6$. Moreover,
since $G$ contains neither $T^{o}_{1,1,7}$ nor $Q^{o}_{1,1,1,7}$, $f$ cannot
be weakly adjacent to any $3$-face or $4$-face across an edge with
multiplicity $6$. We consider the cases based on the value of $a+b+c$.

  * •

If $a+b+c\leqslant 11$, then at most two of $a$, $b$, and $c$ are larger than
or equal to $4$. Recall that in Rule (B) that every inner $3$-face of
$T_{a,b,c}$ with $a+b+c\leqslant 11$ gives charge $\frac{1}{42}$ to each of
its weakly adjacent $3$-faces only across each edge with multiplicity at least
$4$. By Rules (A) and (B), the face $f$ ends with at least
$3-(a+b+c-3)\times\frac{2}{21}-2\times\frac{1}{42}=\frac{68-2(a+b+c)}{21}\geqslant\frac{46}{21}$.

  * •

If $a+b+c\geqslant 12$, then we only need to consider the following
configurations: $T_{1,5,6}$, $T_{2,5,5}$, $T_{4,4,4}$, and $T_{1,6,6}$.

For $T_{1,5,6}$ and $T_{1,6,6}$, the face $f$ of $T_{1,5,6}$ or $T_{1,6,6}$ is
weakly adjacent with $5^{+}$-faces across each edge with multiplicity $6$. So
by Rules (A) and (C), each $f$ of $T_{1,5,6}$ ends with at least
$3-9\times\frac{2}{21}+\frac{9}{105}=\frac{234}{105}>\frac{46}{21}$ and each
$f$ of $T_{1,6,6}$ ends with at least
$3-10\times\frac{2}{21}+2\times\frac{9}{105}=\frac{233}{105}>\frac{46}{21}$.

For $T_{2,5,5}$, since $G$ has neither $T_{2,2,6}^{o}$ nor $Q_{6,6,6,7}^{oo}$,
each $f$ of $T_{2,5,5}$ is weakly adjacent (across each edge of multiplicity
5) with a $5^{+}$-face or an inner $4$-face of the subgraph $Q_{a,b,c,d}$ with
$a+b+c+d\leqslant 5+5+6+6=22$. Thus by Rules (A), (B), and (C), each $f$ of
$T_{2,5,5}$ ends with at least
$3-9\times\frac{2}{21}+2\times\min\\{\frac{1}{21},\frac{9}{105}\\}>\frac{46}{21}$.

Finally, consider an inner $3$-face $f$ of the subgraph $T_{4,4,4}$. By Lemma
4.12, if $f$ of $T_{4,4,4}$ is weakly adjacent to three $3$-faces, then they
are pairwise not weakly adjacent to each other. Since $G$ contains no copy of
$F$, either (a) some face $f^{\prime}$ that is weakly adjacent to $f$ is a
$5^{+}$-face or a $4$-face of $Q_{a,b,c,d}$ with $a+b+c+d\leqslant
4+6+6+6=22$; or (b) every face $f^{\prime}$ that is weakly adjacent to $f$ is
the inner $3$-face of $T_{a,b,c}$ with $a+b+c\leqslant 1+4+6=11$. Hence, by
Rules (A), (B), and (C), $f$ finishes with at least
$3-9\times\frac{2}{21}+\min\\{\frac{1}{21},\frac{9}{105},3\times\frac{1}{42}\\}=\frac{46}{21}$.

We are done.

## Acknowledgments

Jiaao Li is supported by National Key Research and Development Program of
China (No. 2022YFA1006400), National Natural Science Foundation of China (Nos.
12222108, 12131013), Natural Science Foundation of Tianjin (No.
22JCYBJC01520), and the Fundamental Research Funds for the Central
Universities, Nankai University. Zhouningxin Wang is supported by National
Natural Science Foundation of China (Nos. 12301444) and the Fundamental
Research Funds for the Central Universities, Nankai University.

## References

  * [1] O.V. Borodin, S.-J. Kim, A.V. Kostochka, and D.B. West, Homomorphisms from sparse graphs with large girth, J. Combin. Theory, Ser. B, 90 (2004) 147–159.
  * [2] D.W. Cranston and J. Li, Circular flows in planar graphs, SIAM J. Discrete Math., 34 (2020) 497–519.
  * [3] Z. Dvořák and L. Postle, Density of 5/2-critical graphs, Combinatorica, 37 (2017) 863–886.
  * [4] M. Han, H-J. Lai, J. Li, and Y. Wu, Contractible graphs for flow index less than three, Discrete Math., 343 (2020) 112073.
  * [5] M. Han, J. Li, Y. Wu and C.-Q. Zhang, Counterexamples to Jaeger’s circular flow conjecture, J. Combin. Theory, Ser. B, 131 (2018) 1–11.
  * [6] F. Jaeger, On circular flows in graphs, Finite and infinite sets. North-Holland, 37 (1984) 391–402.
  * [7] F. Jaeger, Nowhere-zero flow problems, Selected Topics in Graph Theory, 3 (1988) 71–95.
  * [8] J. Li, H.-J. Lai and R. Luo, Group connectivity, strongly $\mathbb{Z}_{m}$-connectivity, and edge disjoint spanning trees, SIAM J. Discrete Math., 31 (2017) 1909–1922.
  * [9] J. Li, R. Naserasr, Z. Wang, and X. Zhu, Circular flows in mono-directed signed graphs, arXiv:2212.10757, 2022.
  * [10] J. Li, Y. Shi, Z. Wang, and C. Wei, Homomorphisms to small negative even cycles, submitted, 2023.
  * [11] J. Li, Y. Wu, and C.-Q. Zhang, Circular flows via extended Tutte orientations, J. Combin. Theory, Ser. B, 145 (2020) 307–322.
  * [12] L.M. Lovász, C. Thomassen, Y. Wu, and C.-Q. Zhang, Nowhere-zero 3-flows and modulo k-orientations, J. Combin. Theory, Ser. B, 103 (2013) 587–598.
  * [13] C.S.J. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. London Math. Soc., 36 (1961) 445–450.
  * [14] J. Nešetřil and X. Zhu, On bounded tree-width duality of graphs, J. Graph Theory, 23 (1996) 151–162.
  * [15] L. Postle and E. Smith-Roberge, On the density of $C_{7}$-critical Graphs, Combinatorica, 42 (2022) 253–300.
  * [16] W.T. Tutte, On the problem of decomposing a graph into $n$ connected factors, J. the London Math. Society, 1 (1961) 221–230.
  * [17] X. Zhu, Circular chromatic number of planar graphs of large odd girth, Electron. J. Combin., 8 (2001) #25.
  * [18] C.-Q. Zhang, Circular flows of nearly eulerian graphs and vertex-splitting, J. Combin. Theory, 40 (2002) 147–161.