# The saturation number of $K_{3,3}$

Shenwei Huang1, Hui Lei2, Yongtang Shi3, and Junxue Zhang3
1College of Computer Science
Nankai University, Tianjin 300350, China
Email<EMAIL_ADDRESS>
2School of Statistics and Data Science, LPMC & KLMDASR
Nankai University, Tianjin 300071, China
Emails<EMAIL_ADDRESS>
3Center for Combinatorics and LPMC
Nankai University, Tianjin 300071, China
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

A graph $G$ is called $F$-saturated if $G$ does not contain $F$ as a subgraph
(not necessarily induced) but the addition of any missing edge to $G$ creates
a copy of $F$. The saturation number of $F$, denoted by $sat(n,F)$, is the
minimum number of edges in an $n$-vertex $F$-saturated graph. Determining the
saturation number of complete partite graphs is one of the most important
problems in the study of saturation number. The value of $sat(n,K_{2,2})$ was
shown to be $\lfloor\frac{3n-5}{2}\rfloor$ by Ollmann, and a shorter proof was
later given by Tuza. For $K_{2,3}$, there has been a series of study aiming to
determine $sat(n,K_{2,3})$ over the years. This was finally achieved by Chen
who confirmed a conjecture of Bohman, Fonoberova, and Pikhurko that
$sat(n,K_{2,3})=2n-3$ for all $n\geq 5$. In this paper, we prove a conjecture
of Pikhurko and Schmitt that $sat(n,K_{3,3})=3n-9$ when $n\geq 9$.

Keywords: saturation number; complete bipartite graphs; minimum degree

##  1 Introduction

All graphs in this paper are finite and simple. Throughout the paper we use
the terminology and notation of [23]. Given a graph $G$, we use $|G|$, $e(G)$,
$\delta(G)$, and $\Delta(G)$ to denote the number of vertices, the number of
edges, the minimum degree and the maximum degree of $G$, respectively. Let
$\overline{G}$ denote the complement graph of $G$. For any $v\in V(G)$, let
$d_{G}(v)$ and $N_{G}(v)$ denote the degree and neighborhood of $v$ in $G$,
respectively, and let $N_{G}[v]=N_{G}(v)\cup\\{v\\}$. We shall omit the
subscript $G$ when the context is clear. For $A,B\subseteq V(G)$ with $A\cap
B=\emptyset$, let $A\sim B$ denote that every vertex in $A$ is adjacent to
every vertex in $B$. For $S\subseteq V(G)$, we denote by $G[S]$ the subgraph
of $G$ induced by $S$. For positive integer $k$, we let
$[k]=\\{1,2,\ldots,k\\}$. We denote a path, a cycle, a star, and a complete
graph with $n$ vertices by $P_{n}$, $C_{n}$, $S_{n}$, and $K_{n}$,
respectively. For $r\geq 2$ and positive integers $s_{1},\ldots,s_{r}$, let
$K_{s_{1},\ldots,s_{r}}$ denote the complete $r$-partite graph with part sizes
$s_{1},\ldots,s_{r}$.

Given a family of graphs $\mathcal{F}$, a graph $G$ is $\mathcal{F}$-saturated
if no member of $\mathcal{F}$ is a subgraph of $G$, but for any $e\in
E(\overline{G})$, some member of $\mathcal{F}$ is a subgraph of $G+e$. The
saturation number of $\mathcal{F}$, denoted by $sat(n,\mathcal{F})$, is the
minimum number of edges in an $n$-vertex $\mathcal{F}$-saturated graph. If
$\mathcal{F}=\\{F\\}$, we also write $sat(n,\\{F\\})$ as $sat(n,F)$.

Saturation numbers were first studied in 1964 by Erdős, Hajnal, and Moon [14],
who proved that $sat(n,K_{k+1})=(k-1)n-{{k}\choose{2}}$. Furthermore, they
proved that equality holds only for the graph
$K_{k-1}\vee\overline{K_{n-k+1}}$, where $\vee$ denotes the standard graph
joining operation. In 1986, Kászonyi and Tuza in [18] determined $sat(n,F)$
for $F\in\\{S_{k},kK_{2},P_{k}\\}$, and they proved that
$sat(n,\mathcal{F})=O(n)$ for any family $\mathcal{F}$ of graphs. Since then,
there has been extensive research on saturation numbers for various graph
families $\mathcal{F}$.

We briefly survey some results in two main lines of research in this area,
namely the saturation numbers for cycles and complete multipartite graphs. The
study of $sat(n,C_{k})$ was dated back to 1978 when Bollobás [3] asked the
problem of estimating $sat(n,C_{k})$ for $3\leq k\leq n$. Exact values of
$sat(n,C_{k})$ are known only for $k=3,4,5$ [14, 19, 22, 8], and for all even
$n\geq 20$ and odd $n\geq 17$ [11, 12, 13]. For $k\geq 6$, the exact value of
$sat(n,C_{k})$ is not known and only bounds for these numbers have been
obtained. For $k\geq 7$, Barefoot, Clark, Entringer, Porter, Székely, and Tuza
[1] proved that $n(1+\frac{1}{2k+8})\leq sat(n,C_{k})\leq c_{k}n+O(n)$, where
$c_{k}$ is a function of $k$. Later on, Füredi and Kim [16] gave the current
best bounds: $\left(1+\frac{1}{k+2}\right)n-1\leq
sat(n,C_{k})\leq\left(1+\frac{1}{k-4}\right)n+{{k-4}\choose 2}$ for all $k\geq
7$ and $n\geq 2k-5$. In the same paper [16], they conjectured there exists a
$k_{0}$ such that $sat(n,C_{k})=\left(1+\frac{1}{k-4}\right)n+O(k^{2})$ for
all $k\geq k_{0}$. The conjecture remains open, although many researchers have
been working it. It seems that determining the exact value of $sat(n,C_{k})$
even for a particular value of $k$ is a very difficult problem as mentioned by
Faudree, Faudree, and Schmitt[15].

We now mention some results for complete multipartite graphs. When all but at
most one parts have size 1, Pikhurko [20] and Chen, Faudree, and Gould [7]
independently determined the saturation number of complete multipartite graphs
with sufficiently large order. When there are at least two parts of size at
least 2, the exact value was only known for $K_{2,2}$ and $K_{2,3}$. The exact
value for $K_{2,2}$ was first determined by Ollmann [19]. Later on, a shorter
proof was given by Tuza [22]. For $K_{2,3}$, there have been several papers
aiming to determine $sat(n,K_{2,3})$ over the years. This was finally achieved
by Chen [10] who confirmed a conjecture of Bohman, Fonoberova, and Pikhurko
[2] that $sat(n,K_{2,3})=2n-3$ for all $n\geq 5$. For the case where the graph
has $r$ parts and all parts have size 2, Gould and Schmitt [17] conjectured
that $sat(n,K_{2,\ldots,2})=\lceil((4r-5)n-4r^{2}+6r-1)/2\rceil$, and they
proved the conjecture when the minimum degree of the
$K_{2,\ldots,2}$-saturated graphs is $2r-3$. It should be noted that the proof
of all these results are quite technically involved and require significant
efforts. Other than these graphs, no result on the exact value is known. For
general complete multipartite graphs $K_{s_{1},\ldots,s_{r}}$ with
$s_{r}\geq\cdots\geq s_{1}\geq 1$, Bohman, Fonoberova, and Pikhurko [2]
determined the asymptotic bound of $sat(n,K_{s_{1},\ldots,s_{r}})$ as
$n\rightarrow\infty$.

######  Theorem 1.1 ([2])

Let $r\geq 2$ and $s_{r}\geq\cdots\geq s_{1}\geq 1$. Define
$p=s_{1}+\cdots+s_{r-1}-1$. Then, for all large $n$,

$\displaystyle\left(p+\frac{s_{r}-1}{2}\right)n-O(n^{3/4})\leq
sat(n,K_{s_{1},\ldots,s_{r}})\leq{p\choose
2}+p(n-p)+\left\lceil\frac{(s_{r}-1)(n-p)}{2}-\frac{s_{r}^{2}}{8}\right\rceil.$
(1)

In particular,
$sat(n,K_{s_{1},\ldots,s_{r}})=(s_{1}+\ldots+s_{r-1}+0.5s_{r}-1.5)n+O(n^{3/4}).$

###  1.1 Our Contribution

We continue to study the saturation number for complete multipartite graphs.
In light of the known results, studying $sat(n,K_{3,3})$ is the natural next
step. In 2008, Pikhurko and Schmitt [21] conjectured that
$sat(n,K_{3,3})=(3+o(1))n$. By considering the graph obtained from the join of
an edge with a $K_{2,2}$-free 2-regular graph on $n-2$ vertices, it follows
that $sat(n,K_{3,3})\leq 3n-7$. For sufficiently large $n$, this fact can also
be deduced from Eq. (1). In this paper, we determine the exact value of
$sat(n,K_{3,3})$. The main result of this paper is the following theorem.

###### Theorem 1.2

$sat(n,K_{3,3})=\begin{cases}2n&6\leq n\leq 8,\\\\[5.69054pt] 3n-9&n\geq 9.\\\
\end{cases}$

To prove Theorem 1.2, we first prove that $sat(n,K_{3,3})$ is at most the
claimed value in Section 2 by constructing a $n$-vertex $K_{3,3}$-saturated
graph with $2n$ edges when $6\leq n\leq 8$ and $3n-9$ edges when $n\geq 9$.
Then we prove that $sat(n,K_{3,3})$ is at least the claimed value in Section
3.

##  2 Proof of the Upper Bound

In this section, for $n\geq 6$, we construct an $n$-vertex $K_{3,3}$-saturated
graph $G_{n}$ with $sat(n,K_{3,3})$ edges. Let $G$ be a graph as depicted in
Figure 1. Then $G_{n}=G[\\{v_{1},\ldots,v_{n}\\}]$ for $6\leq n\leq 11$. It is
easy to verify that $G_{n}$ ($6\leq n\leq 11$) is $K_{3,3}$-saturated and
$e(G_{n})=2n$ when $6\leq n\leq 8$; $e(G_{n})=3n-9$ when $9\leq n\leq 11$.

###### Definition 2.1

For $n\geq 12$, let $H=\overline{K_{2}}\vee(C_{4}\cup C_{n-9}\cup K_{1})$,
where $V(\overline{K_{2}})=\\{v_{1},v_{2}\\}$,
$C_{4}=v_{3}v_{4}v_{5}v_{6}v_{3}$, $C_{n-9}=v_{7}v_{8}\ldots v_{n-3}v_{7}$,
$V(K_{1})=\\{v_{n-2}\\}$. Let $G_{n}$ be the graph obtained from $H$ by adding
new vertices $\\{v_{n-1},v_{n}\\}$ and new edges
$\\{v_{n-1}v_{3},v_{n-1}v_{5},v_{n}v_{4},v_{n}v_{6}\\}$.

###### Proposition 2.2

For $n\geq 12$, the graph $G_{n}$ defined in Definition 2.1 is
$K_{3,3}$-saturated and has $3n-9$ edges.

_Proof._ Clearly, $e(G)=2(n-4)+(n-5)+4=3n-9$. Firstly, We show that $G_{n}$
has no subgraph isomorphic to $K_{3,3}$. From the structure of $G_{n}$, we see
that $d(v_{n-1})=d(v_{n})=2$ and hence cannot lie in a $K_{3,3}$ subgraph.
Since each vertex of $C_{4}\cup C_{n-9}\cup K_{1}$ has at most two neighbors
in $C_{4}\cup C_{n-9}\cup K_{1}$ and $|\overline{K_{2}}|=2$, we cannot find a
copy of $K_{3,3}$ in $G_{n}$.

Let $xy$ be an edge in the complement of $G_{n}$. It remains to show that the
graph $G^{\prime}$ obtained by adding $xy$ to $G_{n}$ has a $K_{3,3}$
subgraph. Without loss of generality, we consider the following cases.

(a) If $x=v_{1},y=v_{2}$ or $x=v_{n-1},y=v_{n}$ or $x=v_{1},y=v_{n-1}$, then
the subgraph of $G^{\prime}$ induced by
$\\{x,v_{3},v_{5}\\}\cup\\{y,v_{4},v_{6}\\}$ is a $K_{3,3}$.

(b) If $x\in\\{v_{4},v_{6},v_{7},\ldots,v_{n-2}\\}$ and $y=v_{n-1}$, then the
subgraph of $G^{\prime}$ induced by
$\\{x,v_{3},v_{5}\\}\cup\\{y,v_{1},v_{2}\\}$ is a $K_{3,3}$.

(c) If $x=v_{3}$ and $y\in\\{v_{7},\ldots,v_{n-2}\\}$, then the subgraph of
$G^{\prime}$ induced by $\\{x,v_{1},v_{2}\\}\cup\\{y,v_{4},v_{6}\\}$ is a
$K_{3,3}$.

In all cases, $G^{\prime}$ contains a copy of $K_{3,3}$. Hence $G_{n}$ is
$K_{3,3}$-saturated. This completes the proof of Proposition 2.2.

Figure 1: The graph $G$.

##  3 Proof of the Lower Bound

In the rest of the paper, let $G$ be a $K_{3,3}$-saturated graph and $a\in
V(G)$ with $d(a)=\delta(G)$. Obviously, we have $d(a)\geq 2$. We partition
$V(G)$ into four parts $V_{1}$, $V_{2}$, $V_{3}$ and $V_{4}$, where
$V_{1}=N[a]$, $V_{2}=\\{x\in V\backslash V_{1}:|N(x)\cap N(a)|\geq 2$},
$V_{3}=\\{y\in V\backslash(V_{1}\cup V_{2}):|N(y)\cap N(a)|=1$} and
$V_{4}=V\backslash(V_{1}\cup V_{2}\cup V_{3})$. Let
$N_{G}(a)=\\{a_{1},a_{2},\ldots,a_{d(a)}\\}$. Let
$V_{2}=\bigcup_{i=2}^{d(a)}V_{2}^{i}$, where $V_{2}^{i}=\\{x\in
V_{2}:|N(x)\cap V_{1}|=i\\}$. For $i_{1},i_{2},\ldots,i_{s}\in[d(a)]$, let
$V_{i_{1}i_{2}\ldots i_{s}}=\\{x\in V_{2}:N(x)\cap
V_{1}=\\{a_{i_{1}},a_{i_{2}},\ldots,a_{i_{s}}\\}\\}$.

In the following, we will first describe some useful properties of
$K_{3,3}$-saturated graphs.

###### Proposition 3.1

The following statement hold.

(i)

For any $x,y\in V(G)$, if $xy\notin E(G)$, then there are
$\\{x_{1},x_{2}\\}\subseteq N(x)$ and $\\{y_{1},y_{2}\\}\subseteq N(y)$ such
that $\\{x_{1},x_{2}\\}\sim\\{y_{1},y_{2}\\}$.

(ii)

For any $x\in V\setminus V_{1}$ and for $i,j\in[d(a)]$, we have $|N(x)\cap
N(a_{i})\cap N(a_{j})|\leq 2$.

(iii)

For any $x\in V_{4}$ there exists $i,j\in[d(a)]$ such that $|N(x)\cap
N(a_{i})\cap N(a_{j})|=2$. For any $x\in V_{3}$ we have $|N(x)\cap V_{2}|\geq
1$. When $G[V_{1}\backslash\\{a\\}]$ contains no $K_{1,2}$, we have $|N(x)\cap
V_{2}|\geq 2$ for any $x\in V\setminus V_{1}$, and in particular $|V_{2}|\geq
3$.

_Proof._ Since there is a copy of $K_{3,3}$ in $G+xy$, (i) follows. If there
is a vertex $x\in V\setminus V_{1}$ such that $|N(x)\cap N(a_{i})\cap
N(a_{j})|\geq 3$ for some $i,j\in[d(a)]$, then we would obtain a copy of
$K_{3,3}$ in $G$, a contradiction. This proves (ii). Since $ax\notin E(G)$ for
any $x\in V(G)\backslash V_{1}$, we obtain the results in (iii) by (i) and
(ii).

Now we prove the lower bound. First we consider the case that $6\leq n\leq 8$.
For $i\in\\{2,3,4\\}$ and $x\in V_{i}$, we define
$f(x)=|N(x)\cap(V_{1}\cup\dots\cup V_{i-1})|+0.5|N(x)\cap V_{i}|-2$. Let
$s_{i}=\sum_{x\in V_{i}}f(x)$, where $i\in\\{2,3,4\\}$.

To prove $sat(n,K_{3,3})\geq 2n$, we consider the minimum degree of the graph
$G$. If $\delta(G)\geq 4$, then we have $e(G)\geq 2n$. So we assume that
$2\leq\delta(G)\leq 3$. We first observe that one can relate the number of
edges to $s_{2}$, $s_{3}$ and $s_{4}$ in the following way.

$\displaystyle e(G)=$
$\displaystyle~{}e(V_{1})+e(V_{2})+e[V_{1},V_{2}]+e(V_{3})+e[V_{1},V_{3}]+e[V_{2},V_{3}]+e(V_{4})+e[V_{4},V_{2}\cup
V_{3}]$ $\displaystyle=$
$\displaystyle~{}e(V_{1})+2(|V_{2}|+|V_{3}|+|V_{4}|)+s_{2}+s_{3}+s_{4}$
$\displaystyle=$ $\displaystyle~{}e(V_{1})+2(n-|V_{1}|)+s_{2}+s_{3}+s_{4}$

###### Claim 1

If $\delta(G)=2$, then $s_{2}+s_{3}+s_{4}\geq|V_{2}|+|V_{3}|$. If
$e(G[V_{1}\backslash\\{a\\}])\leq 1$ and $\delta(G)\geq 3$, then
$s_{2}+s_{3}+s_{4}\geq|V_{2}|+|V_{3}|+|V_{4}|$. If
$e(G[V_{1}\backslash\\{a\\}])\geq 2$, then $s_{2}+s_{3}+s_{4}\geq
0.5(|V_{2}|+|V_{3}|+|V_{4}|)$.

_Proof._ Suppose that $\delta(G)=2$. Then $f(x)\geq 1$ for any $x\in V_{2}\cup
V_{3}$ and $f(x)\geq 0$ for any $x\in V_{4}$ by proposition 3.1 (i). So
$s_{2}+s_{3}+s_{4}\geq|V_{2}|+|V_{3}|$. Suppose that
$e(G[V_{1}\backslash\\{a\\}])\leq 1$ and $\delta(G)\geq 3$. Then $f(x)\geq 1$
for any $x\in V(G)\backslash V_{1}$ by proposition 3.1 (i) and $n\leq 8$. So
$s_{2}+s_{3}+s_{4}\geq|V_{2}|+|V_{3}|+|V_{4}|$. Suppose that
$e(G[V_{1}\backslash\\{a\\}])\geq 2$. Then for $x\in V_{2}$, $f(x)\geq 0.5$;
for $y\in V_{3}$, $f(y)\geq 0.5$ or there exists a $z\in V_{4}$ such that
$f(z)\geq 1$; for $z\in V_{4}$, $f(z)\geq 0.5$. Thus we have
$s_{2}+s_{3}+s_{4}\geq 0.5(|V_{2}|+|V_{3}|+|V_{4}|)$.

Suppose that $\delta(G)=2$. If $a_{1}a_{2}\in E(G)$, then $e(G)\geq
2n+|V_{2}|+|V_{3}|-3$ by Claim 1. By Proposition 3.1 (iii), we have
$|V_{2}|\geq 3$. So $e(G)\geq 2n$. If $a_{1}a_{2}\notin E(G)$, by proposition
3.1 (i), we have $|V_{2}\cup V_{3}|\geq 4$. So $e(G)\geq 2n$.

Suppose that $\delta(G)=3$. If $n=6$, then $G[N(v)]$ is a complete graph for
any $v\in V(G)$ with $d(v)=3$. Since $av\notin E(G)$ for any $v\in
V(G)\backslash V_{1}$, $e(G)\geq 2n$ by proposition 3.1 (i). If $n=7$, then
$e(G[V_{1}\backslash\\{a\\}])\geq 1$ by proposition 3.1 (i). We have $e(G)\geq
2n$ by proposition 3.1 (i) when $1\leq e(G[V_{1}\backslash\\{a\\}])\leq 2$ and
$e(G)\geq 2n-2+s_{2}+s_{3}+s_{4}\geq 2n-2+0.5(|V_{2}|+|V_{3}|+|V_{4}|)\geq
2n-0.5$ when $e(G[V_{1}\backslash\\{a\\}])=3$. If $n=8$, then $e(G)\geq 2n$
when $e(G[V_{1}\backslash\\{a\\}])=1$ or $3$ by Claim 1. If $n=8$ and
$e(G[V_{1}\backslash\\{a\\}])=0$, then $e(G)=2n+s_{2}+s_{3}+s_{4}-5$. So we
need to show $s_{2}+s_{3}+s_{4}\geq 4.5$. If $|V_{123}|\geq 1$, then
$f(x_{1})\geq 2$ for any $x\in V_{123}$. So
$s_{2}+s_{3}+s_{4}\geq|V_{2}|+|V_{3}|+|V_{4}|+1\geq 5$. If $|V_{123}|=0$ and
$|V_{2}|=3$, then $|V_{2}\cap V_{ij}|=3$ for some $i,j\in[3]$ and $i\neq j$,
say $\\{i,j\\}=[2]$, by Proposition 3.1 (i). Since $d(a_{3})\geq 3$,
$|V_{123}|\geq 1$, a contradiction. If $|V_{123}|=0$ and $|V_{2}|=4$, then we
may assume that $|V_{12}|=|V_{23}|=2$. Since $a_{1}a_{3}\notin E(G)$,
$V_{12}\sim V_{23}$ by Proposition 3.1 (i). Since $va_{3}\notin E(G)$ for
$v\in V_{12}$, this contradicts to Proposition 3.1 (i) if $f(x)=1$ for any
$x\in V_{12}\cup V_{23}$. So $s_{2}+s_{3}+s_{4}\geq 4.5$. If $n=8$ and
$e(G[V_{1}\backslash\\{a\\}])=2$, then $e(G)=2n+s_{2}+s_{3}+s_{4}-3$. So we
need to show $s_{2}+s_{3}+s_{4}\geq 2.5$. If $f(x)=0.5$ for some $x\in
V(G)\backslash V_{1}$, then $f(y)\geq 1$ for some $y\in(V(G)\backslash
V_{1})\cap N(x)$. So $s_{2}+s_{3}+s_{4}\geq 2.5$.

This completes the proof of the lower bound for $6\leq n\leq 8$.

In the following, we will prove the case for $n\geq 9$. According to the
partition of $V(G)$, we define $g(x)=|N(x)\cap(V_{1}\cup\cdots\cup
V_{i-1})|+0.5|N(x)\cap V_{i}|-3$ for any $x\in V_{i}$ and $w_{i}=\sum_{x\in
V_{i}}g(x)$, where $i\in\\{2,3,4\\}$. Thus

$\displaystyle e(G)=$ $\displaystyle
e(V_{1})+e(V_{2})+e[V_{1},V_{2}]+e(V_{3})+e[V_{1},V_{3}]+e[V_{2},V_{3}]+e(V_{4})+e[V_{4},V_{2}\cup
V_{3}]$ $\displaystyle=$ $\displaystyle
e(V_{1})+3(|V_{2}|+|V_{3}|+|V_{4}|)+w_{2}+w_{3}+w_{4}$ $\displaystyle=$
$\displaystyle e(V_{1})+3(n-|V_{1}|)+w_{2}+w_{3}+w_{4}.$ (2)

We partition $V_{4}$ into $V_{4}^{2}$ and $V_{4}^{3}$, where
$V_{4}^{3}=\\{z\in V_{4}:|N(z)\cap(V_{2}\cup V_{3})|\geq 3\\}$ and
$V_{4}^{2}=V_{4}\backslash V_{4}^{3}$. Then we partition $V_{4}^{2}$ into
$V_{4}^{20}$ and $V_{4}^{21}$, where $V_{4}^{20}=\\{z\in V_{4}^{2}:|N(z)\cap
V_{4}|\leq 1\\}$ and $V_{4}^{21}=\\{z\in V_{4}^{2}:|N(z)\cap V_{4}|\geq 2\\}$.

###### Proposition 3.2

For any $\\{x_{1},x_{2}\\}\subseteq V_{ij}$, if $|N(x_{1})\cap N(x_{2})\cap
V_{4}^{20}|\geq 3$, then we have $g(z_{i})=-0.5$ and $g(c_{i})\geq 0.5$ for
any $z_{i}\in N(x_{1})\cap N(x_{2})\cap V_{4}^{20}$ and $c_{i}=N(z_{i})\cap
V_{4}$.

_Proof._ If $|N(x_{1})\cap N(x_{2})\cap V_{4}^{20}|\geq 3$, saying
$\\{z_{1},z_{2},z_{3}\\}\subseteq N(x_{1})\cap N(x_{2})\cap V_{4}^{20}$, then
$d(z_{i})\leq 3$ for $i\in[3]$. For $i,j\in[3]$ and $i\neq j$, since
$z_{i}z_{j}\notin E(G)$, then there must be $d(z_{i})=3$ for otherwise there
is no $K_{2,2}$ between $N(x_{i})$ and $N(x_{j})$ by Proposition 3.1 (i). We
have $g(z_{i})=-0.5$ for any $z_{i}\in N(x_{1})\cap N(x_{2})\cap V_{4}^{20}$.
There exists $z_{i}\in N(x_{11})\cap N(x_{12})\cap V_{4}^{20}$ such that
$z_{i}z_{j},z_{i}z_{k}\notin E(G)$, where $z_{j},z_{k}\in(N(x_{11})\cap
N(x_{12})\cap V_{4}^{20})\backslash z_{i}$. By Proposition 3.1 (i), we have
$\\{x_{1},c_{i}\\}\sim\\{x_{2},c_{j}\\}$ and
$\\{x_{1},c_{i}\\}\sim\\{x_{2},c_{k}\\}$. Note that $c_{j}\neq c_{k}$,
otherwise contrary to $z_{j}z_{k}\notin E(G)$. So $g(c_{i})\geq 0.5$. Since
$z_{i},z_{j},z_{k}\in V_{4}^{20}$, $z_{j}z_{k}\notin E(G)$. Similarly, we have
$g(c_{j})\geq 0.5$ and $g(c_{k})\geq 0.5$.

###  3.1 $\delta(G)=2$

Recall that $N_{G}(a)=\\{a_{1},a_{2}\\}$. By (3), we have $e(G)\geq
3n-7+w_{2}+w_{3}+w_{4}$. Therefore, to prove the lower bound, it suffices to
prove

$\displaystyle w_{2}+w_{3}+w_{4}\geq-2.5.$ (3)

Clearly, $g(z)\geq 0$ for any $z\in V_{2}\cup V_{3}\cup V_{4}^{3}\cup
V_{4}^{21}$ and $-1\leq g(z)\leq-0.5$ for any $z\in V_{4}^{20}$. Thus,
$w_{2}\geq 0,w_{3}\geq 0$. Therefore, to prove (3), it suffices to show that
$w_{4}\geq-2.5$.

Let $V_{4}^{20}=\\{z_{1},z_{2},\ldots,z_{|V_{4}^{20}|}\\}$. By Proposition 3.1
(iii), each vertex $z\in V_{4}^{20}$ has exactly two neighbors in $V_{2}$, so
we let $N(z_{i})\cap V_{2}=\\{x_{i1},x_{i2}\\}$. Note that if $g(z_{i})=-1$,
then $N(z_{i})=\\{x_{i1},x_{i2}\\}$ and so $z_{i}$ has no neighbor in
$V_{4}^{20}$, and if $g(z_{i})=-0.5$, then $d(z_{i})=3$ and $z_{i}$ has one
neighbor in $V_{4}$. If $N(z_{i})\cap V_{4}\neq\emptyset$ for
$i\in[|V_{4}^{20}|]$, we let $c_{i}\in N(z_{i})\cap V_{4}$. By Proposition 3.1
(i) and (ii) and the fact that $\delta(G)=2$, for any $x\in V\setminus V_{1}$,
we have $|N(x)\cap V_{2}|=2$.

First we prove that there are no six pairwise distinct vertices
$x_{1},x_{2},\ldots,x_{6}\in V_{2}$ such that
$\\{x_{1},x_{2}\\}\sim\\{x_{3},x_{4}\\}$,
$\\{x_{3},x_{4}\\}\sim\\{x_{5},x_{6}\\}$ and
$\\{x_{1},x_{2}\\}\sim\\{x_{5},x_{6}\\}$. For otherwise,
$\\{a_{1},a_{2},x_{1}\\}\sim\\{x_{3},x_{4},x_{5}\\}$ and thus
$G[\\{a_{1},a_{2},x_{1},x_{3},_{4},x_{5}\\}]$ contains a $K_{3,3}$, a
contradiction. In particular, this, together with Proposition 3.1 (i), implies
that there are no three vertices in $V_{4}$ whose $g$-values are -1. If
$|V_{4}^{20}|\leq 3$, then $w_{4}\geq-2.5$. So we assume that that
$|V_{4}^{20}|\geq 4$.

###### Claim 2

When $|V_{4}^{20}|\geq 4$, then there is at most one vertex $z$ in
$V_{4}^{20}$ with $g(z)=-1$.

_Proof._ Suppose that, by contradiction, that there are two vertices whose
$g$-values are -1, say $z_{1}$ and $z_{2}$. Then $z_{1}z_{2}\notin E(G)$ and
the $K_{2,2}$ between their neighbors is
$\\{x_{11},x_{12}\\}\sim\\{x_{21},x_{22}\\}$. Since $|V_{4}^{20}|\geq 4$,
there exists a vertex, say $z_{3}$, such that $z_{1}z_{3}$ and $z_{2}z_{3}$
are not in $E(G)$. By Proposition 3.1 (i), we have
$\\{x_{11},x_{12}\\}\sim\\{x_{31},*\\}$ and
$\\{x_{21},x_{22}\\}\sim\\{x_{32},*\\}$. Since $d(z_{3})=3$, there exists
$b\in N(z_{3})$ such that $b\sim\\{x_{11},x_{12},x_{21},x_{22}\\}$ by the
pigeonhole principle. This contradicts that $|N(b)\cap V_{2}|\leq 2$. This
proves the claim.

By Claim 2, if $|V_{4}^{20}|\leq 4$, then $w_{4}\geq-2.5$. So we assume that
that $|V_{4}^{20}|\geq 5$.

###### Claim 3

If there exists a vertex in $V_{4}^{20}$ whose $g$-value is -1, then
$w_{2}+w_{3}+w_{4}\geq-2.5$.

_Proof._ Without loss of generality, we assume that that $g(z_{1})=-1$. Recall
that $z_{1}z_{i}\notin E(G)$ for any $i\in[|V_{4}^{20}|]$. First observe that
there is no $z\in V_{4}^{20}\setminus\\{z_{1}\\}$ with
$z\sim\\{x_{11},x_{12}\\}$. Suppose that not. Then $|N(z)\cup N(z_{1})|=3$,
and this contradicts the fact that $z_{1}z\notin E(G)$ and Proposition 3.1
(i).

Next we prove that there are at least $|V_{4}^{20}|-2$ vertices $z_{i}\in
V_{4}^{20}$ such that $\\{x_{11},x_{12}\\}\sim\\{x_{i1},c_{i}\\}$. Suppose
that not. Then there exist two vertices, say $z_{2}$ and $z_{3}$, such that
$\\{x_{11},x_{12}\\}\sim\\{x_{t1},x_{t2}\\}$ for $t=2,3$. Since $|N(x)\cap
V_{2}|=2$ for any $x\in V\setminus V_{1}$,
$\\{x_{21},x_{22}\\}=\\{x_{31},x_{32}\\}$. Note that $z_{2}z_{3}\in E$ for
otherwise the non-edge $z_{2}z_{3}$ contradicts Proposition 3.1 (i). Since
$|V_{4}^{20}|\geq 5$, there exists a vertex, say $z_{4}$, such that
$z_{4}z_{p}\notin E(G)$ for any $p\in[3]$. By applying Proposition 3.1 (i) to
$z_{1}z_{4}$, we have $\\{x_{4i},c_{4}\\}\sim\\{x_{11},x_{12}\\}$ for some
$i\in\\{1,2\\}$ and thus $x_{4i}\in\\{x_{21},x_{22}\\}$. Since $c_{2}=z_{3}$,
there is no $K_{2,2}$ between $N(z_{2})$ and $N(z_{4})$, contradicting to
Proposition 3.1 (i). This proves the statement.

Now we may assume that that for $i\in\\{3,4,\ldots,|V_{4}^{20}|\\}$, we have
$\\{x_{11},x_{12}\\}\sim\\{x_{i1},c_{i}\\}$. Next we show that $g(c_{i})\geq
0.5$ for any $i\in\\{3,4,\ldots,|V_{4}^{20}|\\}$. Since $c_{i}z_{1}\notin
E(G)$, there exist two neighbors $u$ and $v$ of $c$ such that
$\\{x_{11},x_{12}\\}\sim\\{u,v\\}$. Then $u,v\notin\\{x_{11},x_{12},z_{i}\\}$.
Therefore, $d(c_{i})\geq 5$ and thus $g(c_{i})\geq 0.5$. Now we show that for
$i,j\in\\{3,4,\ldots,|V_{4}^{20}|\\}$ with $i\neq j$, $c_{i}\neq c_{j}$. Since
$c_{i}\notin V_{4}^{20}$, $z_{i}z_{j}\notin E$. By Proposition 3.1 (i), there
is a $K_{2,2}$ between $N(z_{i})$ and $N(z_{j})$. By considering the $K_{2,2}$
between $N(z_{k})$ and $N(z_{1})$ for $k\in\\{i,j\\}$, it follows that the
$K_{2,2}$ between $N(z_{i})$ and $N(z_{j})$ must be
$\\{x_{i2},c_{i}\\}\sim\\{x_{j2},c_{j}\\}$. So $c_{i}\neq c_{j}$. Now we have

$w_{4}\geq
g(z_{1})+g(z_{2})+\sum_{i=3}^{|V_{4}^{20}|}(g(z_{i})+g(c_{i}))\geq-1.5.$

This completes the proof.

By Claim 3, we have $g(z)=-0.5$ for every vertex $z\in V_{4}^{20}$.

###### Claim 4

If $g(z)=-0.5$ for every vertex $z\in V_{4}^{20}$, then
$w_{2}+w_{3}+w_{4}\geq-2.5$.

_Proof._ If $|V_{4}^{20}|\leq 5$, then $w_{4}\geq-2.5$ and so the claim holds.
So we assume that that in the following that $|V_{4}^{20}|\geq 6$. For any
$z_{i}\in V_{4}^{20}\setminus\\{z_{1},c_{1}\\}$, $z_{1}z_{i}\notin E(G)$. By
Proposition 3.1 (i), there is a $K_{2,2}$ between $N(z_{i})$ and $N(z_{1})$.
We consider different types of $K_{2,2}$ as follows.

Type 1 : $\\{x_{11},x_{12}\\}\sim\\{x_{i1},x_{i2}\\}$;

Type 2 : $\\{x_{11},x_{12}\\}\sim\\{x_{i1},c_{i}\\}$;

Type 3 : $\\{x_{1s},c_{1}\\}\sim\\{x_{i1},x_{i2}\\}$, where $s\in\\{1,2\\}$;

Type 4 : $\\{x_{1s},c_{1}\\}\sim\\{x_{it},c_{i}\\}$, where $s,t\in\\{1,2\\}$.

Let $A_{0}=\emptyset$. For $j\in[4]$, let $A_{j}$ be the set of vertices in
$V_{4}^{20}\setminus(A_{0}\cup...\cup A_{j-1})$ that are of Type $j$. Let
$|A_{j}|=m_{j}$ for $j\in[4]$. Note that
$m_{1}+m_{2}+m_{3}+m_{4}=|V_{4}^{20}|-1$. For $j\in[4]$, we define

$C_{j}=\\{c_{i}:z_{i}\in A_{j}\\}.$

Note that $C_{j}$ and $C_{k}$ may intersect where $j\neq k$. Moreover,
$C=\\{c_{1}\\}\cup C_{1}\cup C_{2}\cup C_{3}\cup C_{4}$.

We first claim that if $A_{1}\neq\emptyset$, then we have
$w_{2}+w_{3}+w_{4}\geq-2.5$. Since $|V_{4}^{20}|\geq 6$, there exists a
vertex, say $z_{3}\in V_{4}^{20}$, such that $z_{3}z_{1}\notin E(G)$ and
$z_{3}z_{2}\notin E(G)$. By applying Proposition 3.1 (i) to $z_{1}z_{3}$,
there exist two vertices $u,v\in N(z_{1})$ and two vertices $s,t\in N(z_{3})$
such that $\\{u,v\\}\sim\\{s,t\\}$. We show that $c_{1}\in\\{u,v\\}$ and
$c_{3}\in\\{s,t\\}$. Note first that by Proposition 3.1 (ii), we have
$x_{31}\in\\{x_{21},x_{22}\\}$ and $x_{32}\in\\{x_{11},x_{12}\\}$. So it
cannot be that $\\{u,v\\}=\\{x_{11},x_{12}\\}$ and
$\\{s,t\\}=\\{x_{31},x_{32}\\}$. Suppose that now that
$\\{x_{11},x_{12}\\}\sim\\{x_{31},c_{3}\\}$. Then
$x_{31}\in\\{x_{21},x_{22}\\}$. Since $|N(c_{3})\cap V_{2}|=2$, there is no
$K_{2,2}$ between $N(z_{3})$ and $N(z_{2})$, a contradiction. Suppose that
that $\\{x_{11},c_{1}\\}\sim\\{x_{12},x_{22}\\}$. Then $|N(x_{11})\cap
V_{2}|\geq 3$, which contradicts Proposition 3.1 (ii). So we have proved that
$c_{1}\in\\{u,v\\}$ and $c_{3}\in\\{s,t\\}$. In other words, the $K_{2,2}$
between $z_{1}$ and $z_{3}$ is $\\{x_{11},c_{1}\\}\sim\\{x_{31},c_{3}\\}$.
This implies that $c_{3}\notin V_{4}^{20}$ and this means that $z_{3}$ has no
neighbors in $V_{4}^{20}$. Similarly, the $K_{2,2}$ between $z_{2}$ and
$z_{3}$ is $\\{x_{21},c_{2}\\}\sim\\{x_{31},c_{3}\\}$. Since
$\\{x_{11},x_{12}\\}\sim\\{x_{21},x_{22}\\}$, we have
$x_{31}\in\\{x_{21},x_{22}\\}$ and $x_{32}\in\\{x_{11},x_{12}\\}$. Note that
$V_{4}^{20}$ has at least $|V_{4}^{20}|-4$ vertices that are adjacent to
neither $z_{1}$ nor $z_{2}$, and there are no edges between these vertices.
For any two such vertices, say $z_{3}$ and $z_{4}$, we have that the $K_{2,2}$
between their neighbors is $\\{x_{31},c_{3}\\}\sim\\{x_{42},c_{4}\\}$. So
$c_{4}\neq c_{3}$. This means that for any $z\in V_{4}^{20}$ that is adjacent
to neither $z_{1}$ nor $z_{2}$, its unique neighbor $c\in V_{4}$ has at least
3 neighbors $V_{4}$, and so $g(z)+g(c)\geq 0$. Moreover, for any two such
vertices, their corresponding neighbors in $V_{4}$ are different. Therefore,
$w_{4}\geq-2$. Thus we assume that that $A_{1}=\emptyset$.

We claim that there exists a $z_{i}\in V_{4}^{20}$ such that $c_{i}\notin
V_{4}^{20}$. Suppose that that $c\in V_{4}^{20}$ for any $z\in V_{4}^{20}$.
Let $z_{1},z_{2}\in V_{4}^{20}$ with $z_{1}z_{2}\notin E(G)$. Since
$z_{1}z_{2}\notin E(G)$, we may assume that
$\\{x_{11},x_{12}\\}\sim\\{x_{21},c_{2}\\}$. There is no $K_{2,2}$ between
$N(z_{1})$ and $N(c_{2})$, which contradicts $z_{1}c_{2}\notin E(G)$. So we
may assume that that $c_{1}\notin V_{4}^{20}$. We choose such $z_{1}$, then we
have $|A_{2}|+|A_{3}|+|A_{4}|=|V_{4}^{20}|-1$.

For any $z\in A_{2}$, we have $c\notin V_{4}^{20}$ for otherwise there is no
$K_{2,2}$ between $N(z_{1})$ and $N(c)$ by $cz_{1}\notin E(G)$. This means
that any $z$ in $A_{2}$ has no neighbor in $V_{4}^{20}$. For any two vertices
in $A_{2}$, say $z_{2}$ and $z_{3}$, $z_{2}z_{3}\notin E(G)$. By Proposition
3.1 (i), we have $\\{x_{22},c_{2}\\}\sim\\{x_{32},c_{3}\\}$. This implies that
$C_{2}$ is a clique.

For any two vertices in $A_{3}$, say $z_{4}$ and $z_{5}$. We have
$\\{x_{41},x_{42}\\}=\\{x_{51},x_{52}\\}$ since $|N(c_{1})\cap V_{2}|=2$.
Since $z_{4}z_{5}\notin E(G)$, $\\{x_{41},c_{4}\\}\sim\\{x_{51},c_{5}\\}$.
This implies that $C_{3}$ is a clique.

Suppose that that $G[A_{4}\cup C_{4}]$ is a disjoint union of $\ell$ stars
$S_{1},\ldots,S_{\ell}$, where $S_{i}$ has center $v_{i}$ and $x_{i}$ leaves
for $i=1,\ldots,\ell$. Then $x_{1}+\cdots+x_{\ell}=|A_{4}|$ and
$C_{4}=\\{v_{1},\ldots,v_{\ell}\\}$. It follows that $g(v_{i})\geq
2+0.5(x_{i}+1)-3=0.5(x_{i}-1).$ So

$\sum_{i=1}^{\ell}g(v_{i})\geq\sum_{i=1}^{\ell}0.5(x_{i}-1)=0.5|A_{4}|-0.5\ell.$

On the other hand, $g(c_{1})\geq 2+05(\ell+1)-3=0.5(\ell-1)=0.5\ell-0.5.$
Therefore,

$g(c_{1})+\sum_{i=1}^{\ell}g(v_{i})\geq 0.5|A_{4}|-0.5.$

This implies that

$g(c_{1})+\sum_{c\in C_{4}}g(c)+\sum_{z\in A_{4}}g(z)\geq-0.5.$ (4)

Now we consider the following cases.

Case 1. $|A_{2}|\geq 3$ (or $|A_{3}|\geq 3$).

Since $|A_{2}|\geq 3$, $C_{2}$ is a clique. In particular, every vertex in
$C_{2}$ has at least two neighbors in $V_{4}\setminus V_{4}^{20}$. This
implies that for any $c\in C_{2}$, $g(c)\geq 0.5$ and that every edge
connecting $c$ and a vertex in $V_{4}^{20}$ contributes 0.5 towards $w_{4}$.

Suppose that first that $|A_{3}|\leq 2$. Let $A^{\prime}_{4}=\\{z_{i}\in
A_{4}:c_{i}\in C_{2}\\}$ and $A^{\prime\prime}_{4}=A_{4}\setminus
A^{\prime}_{4}$. By the observation we just made,

$\sum_{z\in A_{2}\cup A^{\prime}_{4}}g(z)+\sum_{c\in C_{2}}g(c)\geq 0,$

and

$\sum_{z\in A^{\prime\prime}_{4}}g(z)+\sum_{c\in C_{4}}g(c)\geq-0.5.$

This implies that $w_{4}\geq(-0.5)+(-1)+(0+-0.5)=-2.$

Now Suppose that that $|A_{3}|\geq 3$. Since $|A_{3}|\geq 3$, $C_{3}$ is a
clique. So every vertex in $C_{3}$ has at least two neighbors in
$V_{4}\setminus V_{4}^{20}$. This implies that for any $c\in C_{3}$, $g(c)\geq
0.5$ and that every edge connecting $c$ and a vertex in $V_{4}^{20}$
contributes 0.5 towards $w_{4}$. Let $A^{\prime}_{4}=\\{z_{i}\in
A_{4}:c_{i}\in C_{2}\cup C_{3}\\}$ and $A^{\prime\prime}_{4}=A_{4}\setminus
A^{\prime}_{4}$. By the observation we just made,

$\sum_{z\in A_{2}\cup A_{3}\cup A^{\prime}_{4}}g(z)+\sum_{c\in C_{2}\cup
C_{3}}g(c)\geq 0,$

and

$\sum_{z\in A^{\prime\prime}_{4}}g(z)+\sum_{c\in C_{4}}g(c)\geq-0.5.$

This implies that $w_{4}\geq-0.5+-0.5=-1$.

Case 2. $|A_{2}|\leq 2$ and $|A_{3}|\leq 2$.

By Equation (4), it follows that

$\sum_{z\in A_{4}}g(z)+\sum_{c\in C_{4}}g(c)+g(c_{1})\geq-0.5.$

If $|A_{2}|<2$ or $|A_{3}|<2$, then $w_{4}\geq-2.5$. So we assume that that
$|A_{2}|=|A_{3}|=2$. Then

$g(c_{1})+\sum_{z\in V_{4}^{20}}g(z)+\sum_{c\in
C_{4}}g(c)\geq-0.5+-1+-1+-0.5=-3.$ (5)

Note that we only take into consideration the edges $[\\{c_{1}\\}\cup
A_{4},C_{4}]$ in (5).

Let $A_{2}=\\{z_{2},z_{3}\\}$. Clearly, $z_{2}z_{3}\notin E(G)$. The $K_{2,2}$
between $N(z_{2})$ and $N(z_{3})$ must be
$\\{x_{22},c_{2}\\}\sim\\{x_{32},c_{3}\\}$. If there is another neighbor in
$N(c_{2})\setminus\\{x_{11},x_{12},z_{2},c_{3}\\}$, then $g(c_{2})\geq 0.5$.
Otherwise, $N(c_{2})=\\{x_{11},x_{12},c_{3},z_{2}\\}$. Note that
$z_{1}c_{2}\notin E(G)$ or $z_{1}c_{3}\notin E(G)$. By symmetry, we assume
that that $c_{2}z_{1}\notin E(G)$. Observe that the $K_{2,2}$ between
$N(z_{1})$ and $N(c_{2})$ must be $\\{x_{11},c_{1}\\}\sim\\{x_{12},c_{3}\\}$.
Thus $g(c_{3})\geq 0.5$. In a conclusion, we find a new positive vertex with
$g$-value at least $0.5$. This completes the proof.

###  3.2 $\delta(G)=3$

We choose a vertex $a$ such that $d(a)=3$ and $e(G[V_{1}])$ is minimum.
Clearly, we have $|V_{123}|\leq 1$. We define $g^{\prime}(x)=|N(x)\cap
V_{1}|+0.5|N(x)\cap(V_{2}\setminus V_{2}^{2})|-3$ for $x\in V_{2}\setminus
V_{2}^{2}$, $g^{\prime}(x)=|N(x)\cap(V_{1}\cup(V_{2}\setminus
V_{2}^{2}))|+0.5|N(x)\cap V_{2}^{2}|-3$ for $x\in V_{2}^{2}$,
$g^{\prime}(y)=|N(y)\cap(V_{1}\cup V_{2})|+0.5|N(y)\cap(V_{3}\cup V_{4})|-3$
for $y\in V_{3}\cup V_{4}$ and $w_{i}^{\prime}=\sum_{x\in
V_{i}}g^{\prime}(x)$, where $i\in\\{2,3,4\\}$. Let $V^{\prime}_{i}=\\{v\in
V_{i}|g^{\prime}(v)<0\\}$, where $i\in\\{2,3,4\\}$. Similar to (3), we have

$\displaystyle
e(G)=e(V_{1})+3(n-|V_{1}|)+w_{2}^{\prime}+w_{3}^{\prime}+w_{4}^{\prime}.$ (6)

And we define $g^{*}(x)$ for $x\in V\setminus V_{1}$. If $g^{\prime}(y)\geq
0.5$ for $y\in V_{3}\cup V_{4}$, then $g^{\prime}(y)$ first send at most $0.5$
charges to its negetive neighbors in $V^{\prime}_{3}\cup V^{\prime}_{4}$
averagly. We denote the results function as $g^{*}$. For $g^{\prime}(x)\geq
0.5$ where $x\in V_{2}$, $g^{\prime}(x)$ send its value to its negetive in
$V^{\prime}_{2}$. After this operation, $g^{\prime}(y)$ second send its value
to its negetive neighbors in $V^{\prime}_{2}$. For convenience, we usually use
$0.25$ and $0.5$ as a basic sending value. For example, if
$\\{x_{1},x_{2}\\}\subseteq N(y)\cap V^{\prime}_{2}$ for $y\in V_{3}$ and
$N(y)\cap|V\setminus V^{\prime}_{4}|\geq 2$, then we have $g^{*}(x_{k})\geq 0$
for $k\in[2]$ as a result of $x_{k}$ can obtain at least $0.5$ from
$g^{\prime}(y)$. We shall consider three different cases in terms of the
number of edges in $G[V_{1}]$.

###### Claim 5

If $e(G[V_{1}])=6$, then
$w_{2}^{\prime}+w_{3}^{\prime}+w_{4}^{\prime}\geq-3.5$.

_Proof._ We first show if $|N(x)\cap N(a_{i})\cap N(a_{j})|\geq 2$ for any
$x\in V_{2}$, then $x\in V_{ij}$. Let $N(x)\cap N(a_{1})\cap
N(a_{2})=\\{x_{1},x_{2}\\}$. Suppose that that $x\notin V_{12}$. Then $x\in
N(a_{3})$. However, $\\{a_{3},x_{1},x_{2}\\}\sim\\{x,a_{1},a_{2}\\}$, a
contradiction. We shall prove the claim by proving $w^{\prime}_{2}\geq-2.5$
and $w^{\prime}_{3}+w^{\prime}_{4}\geq-1$.

We first show that $w^{\prime}_{3}+w^{\prime}_{4}\geq-1$. Note that this is
true if $|V^{\prime}_{3}|+|V^{\prime}_{4}|\leq 2$. So we may assume that
$|V^{\prime}_{3}|+|V^{\prime}_{4}|\geq 3$. If $y_{1}\in V^{\prime}_{3}$, then
$N(y_{1})=\\{a_{i},x_{0},b_{1}\\}$ where $x_{0}\in V_{2}$ and $b_{1}\in
V_{3}\cup V_{4}$. By the choice of $a$, we have $x_{0}\in V_{123}$ and
$N(b_{1})\cap V_{1}=\\{a_{i}\\}$. We first assume that that
$|V^{\prime}_{3}|\geq 3$. We claim that $V^{\prime}_{3}$ is an independent
set. Suppose that, by contradiction, that $y_{1},y_{2}\in V^{\prime}_{3}$ with
$y_{1}y_{2}\in E(G)$. Since $|V^{\prime}_{3}|\geq 3$, there exists a vertex
$y_{3}\in V^{\prime}_{3}$ with $y_{1}y_{3}\notin E(G)$. Similar to $y_{1}$, we
assume that that $N(y_{3})=\\{a_{j},x_{0},b_{3}\\}$, where $b_{3}\in V_{3}$.
Observe that the $K_{2,2}$ between $N(y_{1})$ and $N(y_{2})$ must be
$\\{a_{i},y_{2}\\}\sim\\{x_{0},b_{2}\\}$ or
$\\{x_{0},y_{2}\\}\sim\\{a_{j},b_{2}\\}$. Since $y_{2}\in V^{\prime}_{3}$,
$y_{2}b_{2}\notin E(G)$, a contradiction.

For any $y_{1},y_{2}\in V^{\prime}_{3}$, we have $y_{1}y_{2}\notin E(G)$.
Observe that the $K_{2,2}$ between $N(y_{1})$ and $N(y_{2})$ must be
$\\{a_{i},b_{1}\\}\sim\\{x_{0},b_{2}\\}$ or
$\\{x_{0},b_{1}\\}\sim\\{a_{j},b_{2}\\}$, and thus $b_{1}b_{2}\in E(G)$. This
implies that any neighbor $b$of $y\in V^{\prime}_{3}$ has at least 2 neighbors
in $V_{3}\setminus V^{\prime}_{3}$ and so $g^{\prime}(b)\geq 0.5$. Thus
$w^{\prime}_{3}\geq 0$. We second asssume that $|V^{\prime}_{4}|\geq 3$. We
claim that $V^{\prime}_{3}$ is an independent set. Suppose that not, there are
$z_{1},z_{2}\in V^{\prime}_{4}$ with $z_{1}z_{2}\in E(G)$. There is $z_{3}\in
V^{\prime}_{4}$ and $z_{1}z_{3}\notin E(G)$, but there is no $K_{2,2}$ between
$N(z_{1})$ and $N(z_{3})$, contradiction. Let
$N(z_{i})=\\{x_{i1},x_{i2},c_{i}\\}$ for any $z_{i}\in V^{\prime}_{4}$. For
any two vertices $z_{1}$ and $z_{2}$ in $V^{\prime}_{4}$, $z_{1}z_{2}\notin
E(G)$. Observe that the $K_{2,2}$ between $N(z_{1})$ and $N(z_{2})$ must be
$\\{x_{11},c_{1}\\}\sim\\{x_{21},c_{2}\\}$, and thus $c_{1}c_{2}\in E(G)$. And
for any $z\in V^{\prime}_{4}$, we have $g^{\prime}(c)\geq 0.5$ where
$c=N(z)\cap V_{4}$. Therefore, $w^{\prime}_{4}\geq 0$. In a conclusion, if
$|V^{\prime}_{3}|\geq 3$ and $|V^{\prime}_{3}|\geq 3$, then
$w^{\prime}_{3}+w^{\prime}_{4}\geq 0$. If $|V^{\prime}_{3}|\geq 3$ and
$|V^{\prime}_{4}|\leq 2$ or $|V^{\prime}_{4}|\geq 3$ and $|V^{\prime}_{3}|\leq
2$, then $w^{\prime}_{3}+w^{\prime}_{4}\geq 0+(-1)\geq-1$. If
$|V^{\prime}_{3}|\leq 2$ and $V^{\prime}_{4}\leq 2$ with
$V^{\prime}_{3}\neq\emptyset$ and $V^{\prime}_{4}\neq\emptyset$, then there
are $y\in V^{\prime}_{3}$ and $z\in V^{\prime}_{4}$. And $yz\notin E(G)$. Let
$N(y)=\\{a_{i},x_{0},b\\}$ and $N(z)=\\{x_{1},x_{2},c\\}$. If the $K_{2,2}$
between $N(z)$ and $N(y)$ is $\\{x_{1},x_{2}\\}\sim\\{a_{i},b\\}$, then
$g^{\prime}(b)\geq 0.5$. If the $K_{2,2}$ is $\\{x_{1},c\\}\sim\\{a_{i},*\\}$,
then $g^{\prime}(c)\geq 0.5$. If the $K_{2,2}$ is
$\\{x_{1},c\\}\sim\\{x_{0},b\\}$, then $g^{\prime}(b)\geq 0.5$. There must be
$|V^{\prime}_{3}|=2$ or $|V^{\prime}_{4}|=2$. similar with above, we have
$w^{\prime}_{3}+w^{\prime}_{4}\geq-1$.

Next we prove $w^{\prime}_{2}\geq-2.5$. We may assume that that
$|V^{\prime}_{2}|\geq 6$. Then there exist $|V_{ij}|\geq 2$ for $i,j\in[3]$,
say $V_{12}$. For any two vertice $x_{1},x_{2}\in V^{\prime}_{2}\cap V_{12}$,
then $x_{1}x_{2}\notin E(G)$. Let $N(x_{s})\cap V_{2}=x_{s1}$ for $s\in[2]$.
Let $\\{y_{s1},y_{s2}\\}\subseteq N(x_{s})\cap V_{3}$ and
$\\{z_{s1},z_{s2}\\}\subseteq N(x_{s})\cap V_{4}$ for $s\in[2]$ if they exist.
We consider the cases of $K_{2,2}$ between $N(x_{1})$ and $N(x_{2})$ as shown
in Table 1.

Table 1: The cases of $K_{2,2}$ between $N(x_{1})$ and $N(x_{2})$. Here
$\times$ means that the case is impossible.

$x_{1}$ $x_{2}$ | $\\{a_{j},x_{21}\\}$ | $\\{a_{j},y_{21}\\}$ | $\\{a_{j},z_{21}\\}$ | $\\{x_{21},y_{21}\\}$ | $\\{x_{21},z_{21}\\}$ | $\\{y_{21},y_{22}\\}$ | $\\{y_{21},z_{21}\\}$ | $\\{z_{21},z_{22}\\}$
---|---|---|---|---|---|---|---|---
$\\{a_{i},x_{11}\\}$ | $A_{0}$ | $A_{1}$ | $\times$ | $A$ | $\times$ | $A$ | $\times$ | $\times$
$\\{a_{i},y_{11}\\}$ | $A_{1}$ | $B_{1}$ | $\times$ | $B_{1}$ | $\times$ | $B$ | $\times$ | $\times$
$\\{a_{i},z_{11}\\}$ | $\times$ | $\times$ | $\times$ | $B_{1}$ | $\times$ | $B$ | $\times$ | $\times$
$\\{x_{11},y_{11}\\}$ | $A$ | $B_{1}$ | $B_{1}$ | $A$ | $A$ | $A$ | $A$ | $C$
$\\{x_{11},z_{11}\\}$ | $\times$ | $\times$ | $\times$ | $A$ | $C$ | $A$ | $A$ | $C$
$\\{y_{11},y_{12}\\}$ | $A$ | $B$ | $B$ | $A$ | $A$ | $D$ | $D$ | $F$
$\\{y_{11},z_{11}\\}$ | $\times$ | $\times$ | $\times$ | $A$ | $A$ | $D$ | $G$ | $E$
$\\{z_{11},z_{12}\\}$ | $\times$ | $\times$ | $\times$ | $C$ | $C$ | $F$ | $E$ | $H_{0}$

  1. $A_{0}$:

There is at most one vertex satisfying the case for fixed vertex $x_{1}$.

  2. $A$ and $A_{1}$:

There exists $y\in V_{3}$ such that $|N(y)\cap V_{2}|\geq 2$ and $d(y)\neq 3$.
Thus $g^{\prime}(y)\geq 0.5$.

  3. $B$ and $B_{1}$:

There exists $y\in V_{3}$ such that $y\notin N(a_{3})$ and $|N(y)\cap
V_{3}|\geq 1$. Thus $|N(y)\cap V_{2}|\geq 2$ and $g^{\prime}(y)\geq 0.5$.

  4. $C$:

Since $\\{z_{21},z_{22}\\}\subseteq N(x_{11})\cap N(x_{2})$ and $N(x_{11})\cap
V_{1}\neq N(x_{2})\cap V_{1}$, $|N(z_{21})\cap V_{2}|\geq 3$. Thus
$g^{\prime}(z_{21})\geq 0.5$ and $g^{\prime}(z_{22})\geq 0.5$.

  5. $D$:

If $g^{\prime}(y_{11})=0$ and $g^{\prime}(y_{12})=0$, then
$N(y_{11})=N(y_{12})=\\{a_{3},x_{1},y_{21},y_{22}\\}$ and $y_{11}y_{12}\notin
E(G)$. By Proposition 3.1 (i), we have $g^{\prime}(y_{21})\geq 1$.

  6. $E$:

If
$g^{\prime}(y_{11})=g^{\prime}(z_{12})=g^{\prime}(z_{21})=g^{\prime}(z_{22})=0$,
then we can’t find a $K_{2,2}$ betweeen $N(y_{11})$ and $N(z_{11})$, a
contradiction to Proposition 3.1 (i).

  7. $F$:

If $g^{\prime}(y_{11})=g^{\prime}(z_{12})=0$, then $y_{11}y_{12}\notin E(G)$,
there is no $K_{2,2}$ between $N(y_{11})$ and $N(y_{12})$, we get a
contradiction to Proposition 3.1 (i).

  8. $G$:

If $g^{\prime}(y_{11})=g^{\prime}(z_{11})=0$, then $y_{11}z_{11}\notin E(G)$.
By Proposition 3.1 (i), we have $g^{\prime}(y_{21})\geq 0.5$ and
$g^{\prime}(z_{21})\geq 0.5$.

  9. $H_{0}$:

If $g^{\prime}(z_{11})=0$, then $z_{11}x_{11}\notin E(G)$. By Proposition 3.1
(i), we have $g^{\prime}(y_{21})\geq 0.5$ or $g^{\prime}(b_{1})\geq 0.5$ for
some $b_{1}\in N(x_{1})$.

For cases $A$ through $G$, there is $g^{*}(x_{1})\geq 0$ or $g^{*}(x_{2})\geq
0$. We show that each case except $A_{0}$ can contribute at least $0.25$ to
$g^{\prime}(x_{1})$ or $g^{\prime}(x_{2})$. Cleary, we just need consider
$H_{0}$. If there is $H_{0}$ with
$g^{\prime}(z_{11})=g^{\prime}(z_{12})=g^{\prime}(z_{21})=g^{\prime}(z_{22})=0$,
then $z_{11}z_{12}\notin E(G)$ and $z_{21}z_{22}\notin E(G)$, and thus
$N(z_{ij})\cap V_{2}=\\{x_{1},x_{2}\\}$ for $i,j\in[2]$. In this case
$z_{11}x_{11}\notin E(G)$ where $x_{11}$ is the neighbor of $x_{1}$ in
$V_{2}$, then there is no $K_{2,2}$ between $N(z_{11})$ and $N(x_{11})$, a
contradiction. Therefore, there exists some $g(z_{ij})\geq 0.5$ for
$i,j\in[2]$.

Next we deal with $A_{0}$. Note that we only need to consider the case that
$|V^{\prime}_{12}|=|V^{\prime}_{13}|=|V^{\prime}_{23}|=2$ and for any
$i,j\in[3]$, for otherwise we are done. In this case, we want to find a new
positive vertex. Here we assume that that $x_{1},x_{2}\in V^{\prime}_{12}$,
$x_{3},x_{4}\in V^{\prime}_{23}$ and $x_{5},x_{6}\in V^{\prime}_{13}$. And by
the case of $A_{0}$, $x_{51}\in V_{12}$, $x_{61}\in V_{23}$, $x_{31}\in
V_{12}$ and $x_{41}\in V_{13}$. If there exists $x_{k1}$ with
$g^{\prime}(x_{k1})\geq 0.5$ for some $k\in[4]$, then it is a new positive
vertex. Therefore, we assume that that $g^{\prime}(x_{k1})=0$ for any
$k\in[4]$. We may assume that that $N(x_{31})\cap V_{2}=\\{x_{3},x_{311}\\}$.
The case that $x_{1}x_{31}\notin E(G)$ is similar to the case that
$x_{1}x_{2}\notin E(G)$ except that we have to consider one more case, namely
the case that the $K_{2,2}$ consists of $\\{x_{3},x_{311}\\}$. But it is easy
to check that there is some positive new vertex in that case. For $A_{1}$,
$B_{1}$ and $H_{0}$, they can contribute at least $0.25$ to
$g^{\prime}(x_{1})$ or $g^{\prime}(x_{2})$. This proves that $w_{2}\geq-2.5$.

Therefore, $w_{2}^{\prime}+w_{3}^{\prime}+w_{4}^{\prime}\geq-1+-2.5=-3.5$.

###### Claim 6

If $e(G[V_{1}])=5$, then
$w_{2}^{\prime}+w_{3}^{\prime}+w_{4}^{\prime}\geq-2.5$.

_Proof._ Since $e(G[V_{1}])=5$, we can assume that that
$a_{2}a_{1},a_{2}a_{3}\in E(G)$. For any $y_{i}\in V^{\prime}_{3}$, we have
$d(y_{i})=3$ and let $N(y_{i})=\\{a_{2},x_{i},b_{i}\\}$. Since $d(y_{i})=3$,
$b_{i}\in N(a_{2})\cap N(x_{i})$.

We first show that $w^{\prime}_{3}+w^{\prime}_{4}\geq-1.5$. If
$|V^{\prime}_{3}|+|V^{\prime}_{4}|\leq 3$, then the result holds. So we assume
that that $|V^{\prime}_{3}|+|V^{\prime}_{4}|\geq 4$. We will show that for any
$y\in V^{\prime}_{3}$, $N(y)\cap V_{2}\subseteq\\{x_{0},x_{1}\\}$ and
$|N(x_{1})\cap V^{\prime}_{3}|\leq 2$, where $x_{0}\in V_{123}$ and $x_{1}\in
V_{13}$ is some fixed vertex. Suppose that that there exist $y_{1},y_{2}\in
V^{\prime}_{3}$ with $N(y_{i})=\\{a_{2},x_{i},b_{i}\\}$, $i\in[2]$ and
$x_{0},x_{1},x_{2}$ are pairwise distinct. Since $x_{1}\neq x_{2}$,
$y_{1}y_{2}\notin E(G)$. If there is a $K_{2,2}$ between $N(y_{1})$ and
$N(y_{2})$, then $|N(b_{i})\cap V_{13}|\geq 2$. Then there will be a
$K_{3,3}$, i.e., $\\{a_{1},a_{3},b_{i}\\}\sim\\{x_{1},x_{2},a_{2}\\}$, a
contradiction. And if $|N(x_{1})\cap V^{\prime}_{3}|\geq 3$, then there are
$y_{1},y_{2}\in N(x_{1})\cap V^{\prime}_{3}$ with $y_{1}y_{2}\notin E(G)$.
However, there is no $K_{2,2}$ between $N(y_{1})$ and $N(y_{2})$, a
contradiction. Moreover, if $|N(x_{1})\cap V^{\prime}_{3}|=2$ and
$\\{y_{i},y_{j}\\}=N(x_{1})\cap V^{\prime}_{3}$, then $y_{i}y_{j}\in E(G)$. If
$|V^{\prime}_{3}|\geq 4$ and $V^{\prime}_{4}=\emptyset$, then there must be
$|N(x_{0})\cap V^{\prime}_{3}|\geq 3$. Let $y_{i},y_{j}\in N(x_{0})\cap
V^{\prime}_{3}$ and $y_{i}y_{j}\notin E(G)$. Then $b_{i}b_{j}\in E(G)$. So
$g^{\prime}(b_{i})\geq 0.5$ for any $y_{i}\in N(x_{0})\cap V^{\prime}_{3}$. We
assume that that $V^{\prime}_{4}\neq\emptyset$. Let
$N(z_{i})=\\{x_{i1},x_{i2},c_{i}\\}$. Since $e(G[V_{1}\setminus\\{a\\}])=2$
and $d(z_{i})=3$, $c_{i}x_{i1}\in E(G)$ or $c_{i}x_{i2}\in E(G)$. We delete
such $z_{i}$ from $V^{\prime}_{4}$ if its neighbor $c_{i}$ in $V_{3}\cup
V_{4}$ satisfies that $|N(c_{i})\cap(V_{1}\cup V_{2})|\geq 3$ or
$|N(c_{i})\cap(V_{3}\cup V_{4})\backslash(V^{\prime}_{3}\cup
V^{\prime}_{4})|\geq 2$. When there exists some vertex $z_{1}\in
V^{\prime}_{4}$ and $N(z_{1})\cap(V_{12}\cup V_{23})\neq\emptyset$, consider
$z_{1}a_{k}\notin E(G)$ for $k\in[3]$. By the deleting operation from
$V^{\prime}_{4}$, there are at least four vertices $y_{i}$ such that
$\\{x_{11},x_{12},a_{1}(a_{2})(a_{3})\\}\subseteq N(y_{i})$ for $i\in[4]$.
Since $z_{1}y_{i}\notin E(G)$, $g^{\prime}(y_{i})\geq 0.5$ and
$N(y_{i})\cap(V_{3}\cup V_{4})\setminus(V^{\prime}_{3}\cup
V^{\prime}_{4})\neq\emptyset$. Thus we find four positive vertices that we
don’t use them to offset any negetive vertices. Then we only need to prove
$w^{\prime}_{3}+w^{\prime}_{4}\geq-3.5$. So we can assume that that
$|V^{\prime}_{3}|+|V^{\prime}_{4}|\geq 8$. For any $z_{2}\in V^{\prime}_{4}$
and $z_{1}z_{2}\notin E(G)$, then there are only three possible cases,
$\\{x_{11},x_{12}\\}\sim\\{x_{21},c_{2}\\}$,
$\\{x_{11},c_{1}\\}\sim\\{x_{21},x_{22}\\}$ and
$\\{x_{11},c_{1}\\}\sim\\{x_{21},c_{2}\\}$. If $|V^{\prime}_{3}|\geq 3$, then
we consider $|V^{\prime}_{4}|\geq 8$. If not, we consider
$|V^{\prime}_{4}|\geq 6$. Then there are at least four vertices $z_{2}$ with
$\\{x_{11},x_{12}\\}\sim\\{x_{21},c_{2}\\}$ or
$\\{x_{11},c_{1}\\}\sim\\{x_{21},c_{2}\\}$, we name them $z_{2}$, $z_{3}$ and
$z_{4}$. Since there is no edges in $\\{z_{2},z_{3},z_{4}\\}$, there exists
$c_{2}$ such that $|N(c_{2})\cap(V_{1}\cup V_{2})|\geq 3$ or
$|N(c_{2})\cap(V_{3}\cup V_{4})\backslash(V^{\prime}_{3}\cup
V^{\prime}_{4})|\geq 2$, contradicting with deleting. Therefore,
$w^{\prime}_{3}+w^{\prime}_{4}\geq-3.5$.

When there is no such $z_{1}$, i.e., $V^{\prime}_{4}\subseteq N(V_{13})$. If
$V^{\prime}_{3}\neq\emptyset$, the $K_{2,2}$ between $N(z_{1})$ and $N(y_{1})$
must be $\\{x_{0},b_{1}\\}\sim\\{x_{11},c_{1}\\}$ and the $K_{2,2}$ between
$N(z_{1})$ and $N(z_{2})$ is $\\{x_{11},c_{1}\\}\sim\\{x_{22},c_{2}\\}$. Then
$w^{\prime}_{3}+w^{\prime}_{4}\geq-1.5$. Thus $V^{\prime}_{3}=\emptyset$. If
there exists $z_{1}z_{2}\in E(G)$ and
$\\{x_{11},x_{12}\\}=\\{x_{21},x_{22}\\}$, we consider $V^{\prime}_{2}$. If
$|V^{\prime}_{2}|\leq 1$, then $|V^{\prime}_{4}|\geq 5$. Then
$z_{1}z_{3}\notin E(G)$ and so the $K_{2,2}$ must be
$\\{x_{11},x_{12}\\}\sim\\{x_{31},c_{3}\\}$, and $\\{c_{3},c_{4},c_{5}\\}$ is
a clique, contradicting with the deleting operation. Now we consider
$|V^{\prime}_{2}|\geq 2$. Let $x_{1}\in V^{\prime}_{2}$. Then
$z_{1}x_{1}\notin E(G)$. This implies that there exists a neighbor $x_{11}$ of
$x_{1}$ such that $g^{\prime}(x_{11})\geq 0.5$ having no relation with any
negetive vertex. So $|V^{\prime}_{4}|\geq 5$ and this leads to the same
contradiction as above. If there is no such $z_{1}$ with $z_{1}z_{2}\in E(G)$
and $\\{x_{11},x_{12}\\}=\\{x_{21},x_{22}\\}$, then there is no
$\\{x_{11},x_{12}\\}\sim\\{x_{21},x_{22}\\}$ because when $z_{1}z_{2}\in
E(G)$, then $x_{11}x_{12}\in E(G)$. There always exists $c_{i}$ satisfying the
condition that deletes $z_{i}$, a contradiction.

We now deal with $w^{\prime}_{2}$. We shall prove $w^{\prime}_{2}\geq-1$.
Suppose that that $x_{1},x_{2}\in V^{\prime}_{2}$. Then $x_{1},x_{2}\in
N(a_{2})$ and $x_{1}x_{2}\notin E(G)$. Let $N(x_{1})\cap
V_{1}=\\{a_{i},a_{2}\\}$ and $N(x_{2})\cap V_{1}=\\{a_{j},a_{2}\\}$. Let
$N(x_{s})\cap V_{2}=x_{s1}$ for $s\in[2]$. Let $\\{y_{s1},y_{s2}\\}\subseteq
N(x_{s})\cap V_{3}$ and $\\{z_{s1},z_{s2}\\}\subseteq N(x_{s})\cap V_{4}$ for
$s\in[2]$ if they exist. Note that if $x\in V^{\prime}_{2}$, then
$g^{\prime}(y)\geq 0$ for any $y\in N(x)\cap V_{3}$. For any $x_{11}\in
N(x)\cap V_{2}$, we have $x_{11}\in V_{13}$. We consider the cases of
$K_{2,2}$ between $N(x_{1})$ and $N(x_{2})$ as shown in Table 2.

Table 2: The cases of $K_{2,2}$ between $N(x_{1})$ and $N(x_{2})$. Here
$\times$ means that the case is impossible.

$x_{1}$ $x_{2}$ | $\\{a_{2},x_{21}\\}$ | $\\{a_{2},y_{21}\\}$ | $\\{a_{2},z_{21}\\}$ | $\\{x_{21},y_{21}\\}$ | $\\{x_{21},z_{21}\\}$ | $\\{y_{21},y_{22}\\}$ | $\\{y_{21},z_{21}\\}$ | $\\{z_{21},z_{22}\\}$
---|---|---|---|---|---|---|---|---
$\\{a_{i},x_{11}\\}$ | $\times$ | $\times$ | $\times$ | $A$ | $\times$ | $A$ | $\times$ | $\times$
$\\{a_{i},y_{11}\\}$ | $D$ | $B$ | $\times$ | $B$ | $\times$ | $B$ | $\times$ | $\times$
$\\{a_{i},z_{11}\\}$ | $\times$ | $\times$ | $\times$ | $B$ | $\times$ | $B$ | $\times$ | $\times$
$\\{x_{11},y_{11}\\}$ | $\times$ | $\times$ | $\times$ | $B$ | $B$ | $B$ | $B$ | $B$
$\\{x_{11},z_{11}\\}$ | $\times$ | $\times$ | $\times$ | $B$ | $C$ | $B$ | $B$ | $C$
$\\{y_{11},y_{12}\\}$ | $D$ | $B$ | $B$ | $B$ | $B$ | $B$ | $B$ | $B$
$\\{y_{11},z_{11}\\}$ | $\times$ | $\times$ | $\times$ | $B$ | $B$ | $B$ | $B$ | $B$
$\\{z_{11},z_{12}\\}$ | $\times$ | $\times$ | $\times$ | $B$ | $C$ | $B$ | $B$ | $E$

  1. $A$:

There exists $y\in V_{3}$ such that $|N(y)\cap V_{2}|\geq 3$. Thus
$g^{\prime}(y)\geq 1$.

  2. $B$:

There exists $y\in V_{3}$ such that $|N(y)\cap V_{2}|\geq 2$ and $y$ has a
neighbor in $V_{3}\cup V_{4}$. Thus $g^{\prime}(y)\geq 0.5$.

  3. $C$:

There exists $z\in V_{4}$ such that $|N(y)\cap V_{2}|\geq 3$ and $z$ has a
neighbor in $V_{3}\cup V_{4}$. Thus $g^{\prime}(z)\geq 0.5$.

  4. $D$:

If $g^{\prime}(y_{11})=0$, then $x_{21}=x_{11}$. Since $y_{11}a_{i}\notin
E(G)$, $g^{\prime}(x_{11})\geq 0.5$ or there exists $y\in N(a_{i})\cap V_{3}$
with $g^{\prime}(y)\geq 1$ by $\\{x_{1},x_{11}\\}\subseteq N(y)$.

  5. $E$:

Suppose that $g^{\prime}(z_{st})=0$ for any $s,t\in[2]$. Then we have
$z_{st}\cap V_{2}=\\{x_{1},x_{2}\\}$ and $a_{i}=a_{j}$. Since
$x_{11}z_{11}\notin E(G)$, there exists $b\in V_{3}\cup V_{4}$ such that
$\\{x_{1},x_{2}\\}\subseteq N(b)\cap V_{2}$. If $d(b)\geq 4$, then
$g^{\prime}(b)\geq 0.5$. Otherwise, we have $x_{11}=x_{21}$. Let
$x^{\prime}\in(V_{2}^{2}\backslash V_{12}\cup\\{x_{11}\\})$. Then there exists
$b^{\prime}\in N(x_{1})\cap N(x_{2})\cap N(x^{\prime})\cap(V_{3}\cup V_{4})$
and $d(b^{\prime})\geq 4$. So $g^{\prime}(b^{\prime})\geq 0.5$.

In each case, we get one vertex with positive charge, which sends at least
$0.25$ charges to its neighbors with negative charge.

###### Claim 7

If $e(G[V_{1}])\leq 4$, then $w_{2}+w_{3}+w_{4}\geq-0.5$.

_Proof._ Suppose that that $e(G[V_{1}])\leq 4$. For any $v\in V_{2}\cup
V_{3}$, we have $g(v)\geq 0$. Thus $w_{2}\geq 0$ and $w_{3}\geq 0$. We have
$g(z)\geq-0.5$ for any $z\in V_{4}^{20}$ and $g(z)\geq 0$ for any $z\in
V_{4}\backslash V_{4}^{20}$. By (3), we shall prove

$\displaystyle w_{4}\geq-0.5.$ (7)

If $|V_{4}^{20}|\leq 1$, then $w_{4}\geq-0.5$ and (7) holds. Thus we assume
that that $|V_{4}^{20}|\geq 2$. If $c_{i}\in N(z_{i})$ where $z_{i}\in
V_{4}^{20}$, $|N(c_{i})\cap(V_{2}\cup V_{3})|\geq 3$ or
$|N(c_{i})\cap(V_{4}\setminus V_{4}^{20})|\geq 2$, then we may delete all such
$z_{i}$ from $V_{4}^{20}$.

Since $z_{1}a_{i}\notin E(G)$, it follow from some careful case analysis that
we can find some positive $g$-value vertices such that the sum of their
$g$-values is at least 2 without calculating the edges incident with vertices
in $V_{4}^{20}$. If $|V_{4}^{20}|\leq 5$, then $w_{4}\geq-0.5$ and we are
done. So we assume that that $|V_{4}^{20}|\geq 6$.

For any $z_{1}z_{i}\notin E(G)$ where $z_{1},z_{i}\in V_{4}^{20}$, the
possible cases between their neighbors are as follows.

Case 1 : $\\{x_{11},x_{12}\\}\sim\\{x_{i1},x_{i2}\\}$;

Case 2 : $\\{x_{11},x_{12}\\}\sim\\{x_{i1},c_{i}\\}$;

Case 3 : $\\{x_{1s},c_{1}\\}\sim\\{x_{i1},c_{i}\\}$;

Case 4 : $\\{x_{1t},c_{1}\\}\sim\\{x_{i1},x_{i2}\\}$.

If there are two vertices $z_{2},z_{3}$ of Case 1, then
$\\{x_{21},x_{22}\\}=\\{x_{31},x_{32}\\}$ for otherwise there is a $K_{3,3}$:
$\\{a_{i},x_{11},x_{12}\\}\sim\\{x_{21},x_{22},x_{31}\\}$. If there exists
$z_{2}$ of Case 1 and $z_{3}$ of Case 2, then $x_{31}\in\\{x_{21},x_{22}\\}$
and if $z_{2}z_{3}\notin E(G)$, then there is no proper $K_{2,2}$, a
contradiction. By the deleting operation from $V_{4}^{20}$, there is at most
one vertex of Case 3 and if $z_{4},z_{5}$ of Case 4, then
$\\{x_{41},x_{42}\\}=\\{x_{51},x_{52}\\}$. Since $|V_{4}^{20}|\geq 6$, then it
follows that $z_{i}$ should be deleted from $V_{4}^{20}$, a contradiction.

###  3.3 $\delta(G)=4$

We choose a vertex $a$ such that $d(a)=4$ and $e(G[V_{1}])$ is minimum. We
consider several cases according to the subgraphs induced by
$V_{1}\setminus\\{a\\}$.

###### Claim 8

If $G[V_{1}\backslash\\{a\\}]$ contains no $K_{1,2}$, then we have $e(G)\geq
3n-9$.

_Proof._ Since $G[V_{1}\backslash\\{a\\}]$ contains no $K_{1,2}$, $g(x)\geq 0$
for any $x\in V(G)\backslash V_{1}$. Moreover, $g(x)\geq k-2$ for any $x\in
V_{2}^{k}$, where $2\leq k\leq 4$. Then $e(G)\geq 3n-11+w_{2}+w_{3}+w_{4}$. We
shall prove

$\displaystyle w_{2}+w_{3}+w_{4}\geq 1.5-e(G[V_{1}\backslash\\{a\\}]).$ (8)

If $V_{2}^{4}\neq\emptyset$ or $|V_{2}^{3}|\geq 2$, then (8) holds. Suppose
that that $V_{2}^{3}=\\{x_{1}\\}$ and $a_{1}x_{1}\notin E(G)$. If
$V_{4}^{3}\neq\emptyset$, then $w_{2}+w_{4}\geq 1.5$ and so (8) holds. So we
assume that that $V_{4}^{3}=\emptyset$. Then $g(x)\geq 0.5$ for any $x\in
V_{3}$. Thus we assume that that $V_{3}=\emptyset$. By Proposition 3.1 (i)
applied to $a_{1}x_{1}\notin E(G)$, there are $\\{a_{11},a_{12}\\}\subseteq
N(a_{1})$ and $\\{x_{11},x_{12}\\}\subseteq N(x_{1})$ such that
$\\{a_{11},a_{12}\\}\sim\\{x_{11},x_{12}\\}$. Note that
$\\{a_{11},a_{12}\\}\subseteq V_{2}$ and there exists $x_{1i}\in V_{2}$ for
$i\in[2]$. So $g(x_{1i})\geq 0.5$ and (8) holds.

Suppose that that $V_{2}^{3}=\emptyset$. assume that that
$V_{12}\neq\emptyset$ and $x_{1}\in V_{12}$. Since
$x_{1}a_{3},x_{1}a_{4}\notin E(G)$, there are
$\\{x_{11},x_{12},x_{13},x_{14}\\}\subseteq N(x_{1})$,
$\\{a_{31},a_{32}\\}\subseteq N(a_{3})$, $\\{a_{41},a_{42}\\}\subseteq
N(a_{4})$ such that $\\{x_{11},x_{12}\\}\sim\\{a_{31},a_{32}\\}$ and
$\\{x_{13},x_{14}\\}\sim\\{a_{41},a_{42}\\}$. Suppose that that
$a_{31}=a_{4}$. Then $g(x_{11})\geq 0.5$ by Proposition 3.1 (iii) and (8)
holds. Suppose that that $a_{42}\in V_{3}$. Then $\\{x_{13},x_{14}\\}\subseteq
V(G)\backslash V_{1}$. If $|N(a_{42})\cap(V_{2}\cup V_{3})|\geq 4$, then
$g(a_{42})\geq 0.5$. Otherwise we have $g(z)\geq 0.5$ for any $z\in
N(a_{42})\cap V_{4}$. By Proposition 3.1 (iii), we have $|x_{1i}\cap
V_{2}\backslash\\{x_{1},a_{41}\\}|\geq 1$ for $i\in\\{3,4\\}$. Hence,
$g(x_{1i})\geq 0.5$ when $x_{1i}\in V_{2}\cup V_{3}$; $g(x_{1i})\geq 1$ when
$x_{1i}\in V_{4}$, where $i\in\\{3,4\\}$. Thus (8) holds.

Suppose that that $\\{a_{31},a_{32},a_{41},a_{42}\\}\subseteq V_{2}$. If
$\\{a_{31},a_{32}\\}\cap\\{a_{41},a_{42}\\}\neq\emptyset$, then $x_{1i}\in
V(G)\backslash V_{1}$ for $i\in[4]$. If
$|\\{a_{31},a_{32}\\}\cap\\{a_{41},a_{42}\\}|=1$, then $g(x_{1i})\geq 0.5$ for
$i\in[4]$, and in particular, $g(x_{1i})\geq 1$ if there exists $i\in[2]$ and
$j\in\\{3,4\\}$ such that $x_{1i}=x_{1j}$. Suppose that that
$\\{a_{31},a_{32}\\}=\\{a_{41},a_{42}\\}$. If
$\\{x_{11},x_{12}\\}\neq\\{x_{13},x_{14}\\}$ or
$e(G[V_{1}\backslash\\{a\\}])\geq 1$, then (8) holds. Otherwise since
$a_{1}a_{31}\notin E(G)$, there exists $\\{a_{11},a_{12}\\}\subseteq N(a_{1})$
and $\\{a_{311},a_{312}\\}\subseteq N(a_{31})$ such that
$\\{a_{311},a_{312}\\}\sim\\{a_{11},a_{12}\\}$. If
$a_{311}\notin\\{x_{11},x_{12}\\}$, then $g(a_{311})\geq 0.5$, and (8) holds.
If $\\{a_{311},a_{312}\\}=\\{x_{11},x_{12}\\}$, then $g(x_{11})\geq 1$ and
$g(x_{12})\geq 1$. Thus (8) holds. Suppose that that
$\\{a_{31},a_{32}\\}\cap\\{a_{41},a_{42}\\}=\emptyset$. Then there exist
$x_{1i}\in V(G)\backslash V_{1}$ and $x_{1j}\in V(G)\backslash V_{1}$ for
$i\in[2]$ and $j\in\\{3,4\\}$, say $x_{11}$ and $x_{13}$. Thus $g(x_{11})\geq
0.5$, $g(x_{13})\geq 0.5$. If there exists $x_{1i}\in V(G)\backslash V_{1}$
for $i\in\\{2,4\\}$, then (8) holds. Otherwise since there exists $a_{i}\in
V_{1}$ such that $a_{i}a_{31}\notin E(G)$, there exists
$\\{a_{i1},a_{i2}\\}\subseteq N(a_{i}),\\{a_{311},a_{312}\\}\subseteq
N(a_{31})$ such that $\\{a_{311},a_{312}\\}\sim\\{a_{11},a_{13}\\}$. If there
exists $a_{311}\notin\\{x_{11},x_{13}\\}$, then $g(a_{311})\geq 0.5$ and (8)
holds. If $\\{a_{311},a_{312}\\}=\\{x_{11},x_{13}\\}$, then $g(x_{13})\geq 1$
and (8) holds.

Next we consider cases where $G[V_{1}\backslash\\{a\\}]$ contains a copy of
$K_{1,2}$. Since $G$ contains no $K_{3,3}$, for any $a_{i}\in N(a)$, if
$a_{i}a_{j},a_{i}a_{k}\in E(G)$, then $|N(x)\cap V_{jk}|\leq 1$ for any $x\in
N(a_{i})\cap(V_{3}\cup V_{4})$.

###### Claim 9

When $G[V_{1}\setminus\\{a\\}]$ is a star with $a_{1}$ is the center,
$w^{\prime}_{2}+w^{\prime}_{3}+w^{\prime}_{4}\geq-0.5$.

We shall prove $w^{\prime}_{2}+w^{\prime}_{3}+w^{\prime}_{4}\geq-0.5$. For any
$x\in V^{\prime}_{2}$ and $y\in N(x)\cap V_{3}$, we have $g^{\prime}(y)\geq
0.5$. If $|N(x)\cap V_{3}|\geq 2$ or $|N(y)\cap V_{2}|\geq|N(y)\cap
V^{\prime}_{2}|+1$ for $y\in N(x)\cap V_{2}$, then $g^{*}(x)\geq 0$. Now for
any $x\in V^{\prime}_{2}$, we assume that $|N(x)\cap V_{3}|\leq 1$ and
$N(y)\cap V_{2}\subseteq V^{\prime}_{2}$ for any $y\in N(x)\cap V_{3}$. Let
$x_{1},x_{2}\in V^{\prime}_{2}$. Since $G[V_{1}\setminus\\{a\\}]$ is a star,
$x_{1}x_{2}\notin E(G)$. Let $N(x_{s})\cap V_{2}=x_{s1}$ for $s\in[2]$. Let
$\\{y_{s1},y_{s2}\\}\subseteq N(x_{s})\cap V_{3}$ and
$\\{z_{s1},z_{s2}\\}\subseteq N(x_{s})\cap V_{4}$ for $s\in[2]$ if they exist.
We consider the cases of $K_{2,2}$ between $N(x_{1})$ and $N(x_{2})$ as shown
in Table 3.

Table 3: The cases of $K_{2,2}$ between $N(x_{1})$ and $N(x_{2})$. Here
$\times$ means that the case is impossible.

$x_{1}$ $x_{2}$ | $\\{a_{2},x_{21}\\}$ | $\\{a_{2},y_{21}\\}$ | $\\{a_{2},z_{21}\\}$ | $\\{x_{21},y_{21}\\}$ | $\\{x_{21},z_{21}\\}$ | $\\{y_{21},z_{21}\\}$ | $\\{z_{21},z_{22}\\}$
---|---|---|---|---|---|---|---
$\\{a_{1},x_{11}\\}$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$
$\\{a_{1},y_{11}\\}$ | $\times$ | $A$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$
$\\{a_{1},z_{11}\\}$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$
$\\{x_{11},y_{11}\\}$ | $\times$ | $\times$ | $A$ | $\times$ | $\times$ | $\times$ | $C$
$\\{x_{11},z_{11}\\}$ | $\times$ | $\times$ | $\times$ | $\times$ | $D$ | $\times$ | $D$
$\\{y_{11},z_{11}\\}$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | $B$ | $B$
$\\{z_{11},z_{12}\\}$ | $\times$ | $\times$ | $\times$ | $B$ | $D$ | $B$ | $E$

  1. $A$:

If $d(y_{11})\geq 5$, then $g^{\prime}(y_{11})$ can send at least $0.5$
charges to $x_{1}$. If $d(y_{11})=4$, then
$N(y_{11})=\\{a_{2},y_{21}(z_{21}),x_{1},x_{3}\\}$ and $N(x_{2})\cap
V_{2}\subseteq N(x_{3})\cap V_{2}$. Suppose that that $G[V_{1}\setminus{a}]$
is a $K_{1,3}$. There is a $K_{1,3}$ in $N(y_{11})$, thus $x_{1}x_{3}\in
E(G)$, a contradiction. Suppose that $K_{1,2}\subseteq G[V_{1}\setminus{a}]$
and $K_{1,3}\nsubseteq G[V_{1}\setminus{a}]$. Since $y_{11}a_{4}\notin E(G)$,
either $g^{*}(x_{1})\geq 0$ or $g^{*}(x_{2})\geq 0$.

  2. $B$:

For some $i\in[2]$, since $d(y_{i1})\geq 5$ and $|N(y_{i1}\cap(V_{3}\cup
V_{4})|\geq 2$, $g^{\prime}(y_{i1})\geq 1$. Thus $g^{*}(x_{i})\geq 0$.

  3. $C$:

Since $d(y_{11})\geq 5$ and $g^{\prime}(y_{11})\geq 1$, it can send at least
$0.5$ charges to $x_{1}$, then $g^{*}(x_{1})\geq 0$.

  4. $D$:

If $x_{11}x_{21}\in E(G)$, then $g^{\prime}(x_{i1})\geq 0.5$ and
$g^{\prime}(x_{i1})$ can sent $0.25$ charges to $x_{i}$ for $i\in[2]$. Since
$g^{\prime}(z_{i1})\geq 0.5$, it can sent $0.25$ charges to $x_{i}$ for
$i\in[2]$. Thus $g^{*}(x_{i})\geq 0$ for $i\in[2]$.

  5. $E$:

For some $i\in[2]$, if $g^{\prime}(z_{ij})\geq 0.5$ for $j\in[2]$, then
$g^{*}(x_{i})\geq 0$. Otherwise, assume that $g^{\prime}(z_{11})=0$ and
$g^{\prime}(z_{21})=0$. Let $N(z_{i1})=\\{x_{i},x_{i0},z_{j1},z_{j2}\\}$,
where $\\{i,j\\}=[2]$. Suppose that $G[V_{1}\setminus{a}]$ is a $K_{1,3}$.
Then $N(z_{11})$ contains a $K_{1,3}$. Since $x_{i}x_{i0}\notin E(G)$ and
$z_{j1}z_{j2}\notin E(G)$, there is no $K_{1,3}$ in $N(z_{11})$, a
contradiction. Suppose that $K_{1,2}\subseteq G[V_{1}\setminus{a}]$ and
$K_{1,3}\nsubseteq G[V_{1}\setminus{a}]$. Since $z_{11}a_{4}\notin E(G)$, then
either there are two vertices $y_{11},y_{12}\in N(x_{1})\cap N(a_{4})$ or
there is $g^{\prime}(z_{21})\geq 1$ such that $z_{21}$ can send at least $0.5$
charges to $x_{2}$. Thus $g^{\prime}(x_{1})\geq 0$ or $g^{\prime}(x_{2})\geq
0$.

In the following, we may assume that $G[N(v)]$ is not a star for any $v\in
V(G)$ with $d(v)=4$.

###### Claim 10

When $G[V_{1}\setminus\\{a\\}]=P_{4}=a_{1}a_{2}a_{3}a_{4}$,
$w^{\prime}_{2}+w^{\prime}_{3}+w^{\prime}_{4}\geq-1.5$.

_Proof._ We may assume that that $|V^{\prime}_{2}|\geq 4$ otherwise the result
will naturally hold. Let $U=\\{b\in V_{4}|~{}d(b)=4~{}\text{and}~{}|N(b)\cap
V_{2}|=|N(b)\cap V^{\prime}_{2}|=3\\}$. For any $v\in(V_{3}\cup
V_{4})\setminus U$ with $g^{\prime}(v)\geq 0.5$, we let $b$ send $0.25$
charges to every $x_{1}\in N(b)\cap V^{\prime}_{2}$. For any $x\in
V^{\prime}_{2}$, if $N(x)\cap U\neq\emptyset$ or $\\{b_{1},b_{2}\\}\subseteq
N(x)\cap(V_{3}\cup V_{4})$ with $g^{\prime}(b_{i})>0$, where $i\in[2]$ , then
$g^{*}(x)\geq 0$.

Case 1 Let $b\in U$. Let $b_{1}\in N(x)\cap U\neq\emptyset$ and
$N(b_{1})=\\{x_{1},x_{2},x_{3},b_{11}\\}$, where $\\{x_{1},x_{2},x_{3}\\}\in
V^{\prime}_{2}$ and $b_{11}\in(V_{3}\cup V_{4})$. Since $G[N(b_{1})]$ is not a
star and $e(G[N(b_{1})])\geq 3$, we may assume that
$x_{1}b_{11},x_{2}x_{3},x_{2}b_{11}\in E(G)$, $x_{1},x_{2}\in V_{13}$ and
$x_{3}\in V_{24}$ by Proposition 3.1 (ii). Since $b_{1}a_{1}\notin E(G)$, we
consider the cases of $K_{2,2}$ between $N(b_{1})$ and $N(a_{1})$. If
$\\{x_{1},x_{2}\\}\sim\\{y_{1},y_{2}\\}$, where $y_{1},y_{2}\in N(a_{1})\cap
V_{3}$, then $g^{*}(x_{1})\geq 0$ and $g^{*}(x_{2})\geq 0$. We let $b_{1}$
send $0.5$ charges to $x_{3}$, thus $g^{*}(x_{3})\geq 0$. If
$\\{x_{3},b_{11}\\}\sim\\{a_{2},y_{1}\\}$, where $y_{1}\in
N(a_{1})\cap(V_{3}\cup V_{4})$, then $g^{\prime}(b_{11})\geq 1$. We let
$b_{11}$ send $0.5$ charges to $x_{1}$ and $x_{2}$, respectively, and $b_{1}$
send $0.5$ charges to $x_{3}$. Thus $g^{*}(x_{i})\geq 0$ for $i\in[3]$. If
$\\{x_{1},b_{11}\\}\sim\\{y_{1},y_{2}\\}$, where $y_{1}\in
N(a_{1})\cap(V_{3}\cup V_{4})$, then $g^{*}(x_{1})\geq 0$ by taking $0.5$
charges from $y_{1}$ and $y_{2}$. Since $g^{\prime}(b_{11})\geq 0.5$ and
$g^{\prime}(b_{1})\geq 0.5$, $g^{*}(x_{2})\geq 0$ and $g^{*}(x_{3})\geq 0$. We
denote the cases $\\{x_{3},b_{11}\\}\sim\\{a_{2},x_{2}\\}$ and
$\\{x_{3},b_{11}\\}\sim\\{x_{2},y_{1}\\}$ as $A$ and $B$, where $y_{1}\in
N(a_{1})\cap(V_{3}\cup V_{4})$, respectively. Since $b_{1}a_{4}\notin E(G)$,
the cases are the same as above. We denote the cases $A$ and $B$ as
$A^{\prime}$ and $B^{\prime}$ correspondingly. Clearly, if $A$, $B$,
$A^{\prime}$ and $B^{\prime}$ occur independently, then we obtain
$g^{*}(x_{i})\geq 0$ for $i\in[3]$. Suppose that two of them occur. Notice
that $A$ and $A^{\prime}$ cannot occur at the same time. If $A$ and
$B^{\prime}$ (or $B$ and $A^{\prime}$) occur, then $g^{\prime}(b_{11})\geq 1$.
Since $g^{\prime}(b_{1})\geq 0.5$, $g^{*}(x_{i})\geq 0$ for $i\in[3]$. If $B$
and $B^{\prime}$ occur, then $g^{\prime}(b_{11})\geq 0.5$, and $x_{2}$ and
$x_{3}$ take $0.25$ charges from some $y\in V_{3}$. Thus $g^{*}(x_{i})\geq 0$
for $i\in[3]$. This complete the proof of Case 1.

By symmetry, we only need to consider the vertices in
$V^{\prime}_{2}\cap(V_{34}\cup V_{24}\cup V_{23})$. If $x_{1}\in
V^{\prime}_{2}\cap V_{34}$, then $x_{11}\in V_{24}$ and
$g^{\prime}(x_{11})\geq 0$, where $x_{11}=N(x_{1})\cap V_{2}$. Suppose that
$d(x_{1})=4$. Let $N(x_{1})=\\{a_{3},a_{4},x_{11},b_{1}\\}$. Since
$G[N(x_{1})]$ is not a star and $e(N(x_{1}))\geq 3$, either $b_{1}a_{3}\in
E(G)$ or $x_{11}b_{1}\in E(G)$. We first consider the case when
$b_{1}x_{11}\in E(G)$. For any $x\in N(b_{1})\cap V^{\prime}_{2}$, we let
$b_{1}$ send $0.5$ charges to $x$. Thus $g^{*}(b_{1})\geq 0$ and $g^{*}(x)\geq
0$ if $g^{\prime}(b_{1})\geq 1$ or $|N(b_{1})\cap V^{\prime}_{2}|=1$ when
$g^{\prime}(b_{1})=0.5$. If $|N(b_{1})\cap V^{\prime}_{2}|=2$ and
$g^{\prime}(b_{1})=0.5$, then $b_{1}\in V_{4}$ and $d(b_{1})=4$. Let
$N(b_{1})=\\{x_{1},x_{11},x_{2},b_{11}\\}$, where $b_{11}\in(V_{3}\cup V_{4})$
and $x_{2}\in V^{\prime}_{2}\cap(V_{34}\cup V_{24})$. Since $G[N(b_{1})]$ is
not a star and $e(N(b_{1}))\geq 3$, either $x_{1}x_{11}x_{2}b_{11}$ or
$x_{1}x_{11}b_{11}x_{2}$ is a $P_{4}$ by Claim 10. Since $b_{1}a_{1}\notin
E(G)$, we consider the cases of $K_{2,2}$ between $N(b_{1})$ and $N(a_{1})$ as
shown in Table 4. Let $\\{x_{3},x_{4}\\}\subseteq N(a_{1})\cap V_{2}$ and
$\\{y_{11},y_{12}\\}\subseteq N(a_{1})\cap V_{3}$ if they exist.

Table 4: The cases of $K_{2,2}$ between $N(b_{1})$ and $N(a_{1})$. Here
$\times$ means that the case is impossible.

$b_{1}$ $a_{1}$ | $\\{a_{2},x_{3}\\}$ | $\\{a_{2},y_{11}\\}$ | $\\{x_{3},x_{4}\\}$ | $\\{x_{3},y_{11}\\}$ | $\\{y_{11},y_{12}\\}$
---|---|---|---|---|---
$\\{x_{11},b_{11}\\}$ | $A$ | $B$ | $C$ | $G$ | $G$
$\\{x_{2},b_{11}\\}$ | $D$ | $E$ | $\times$ | $F$ | $F$
$\\{x_{2},x_{11}\\}$ | $\times$ | $F$ | $\times$ | $F$ | $F$

  1. $A$:

If $x_{11}b_{11}\notin E(G)$, then $x_{11}x_{2}\in E(G)$ and $x_{2}\in
V_{34}$. If $x_{3}\in V^{\prime}_{2}$, then $d(b_{11})\geq 5$ and
$g^{\prime}(b_{11})\geq 1$ since there is no edges in
$\\{a_{2},x_{2},x_{3}\\}$. If $x_{11}b_{11}\in E(G)$, then
$\\{a_{2},x_{11},x_{2},x_{3},b_{1}\\}\subseteq N(b_{11})$ and
$g^{\prime}(b_{11})\geq 1$. So $g^{*}(x_{2})\geq 0$ by taking $0.5$ charges
from $b_{11}$.

  2. $B$:

Since $\\{x_{2},a_{2},b_{1},y_{11}\\}\subseteq N(b_{11})$ and $x_{2}\in
V_{34}\cup V_{24}$, $g^{\prime}(b_{11})\geq 1$ by Proposition 3.1 (ii). Thus
$g^{*}(x_{2})\geq 0$ by taking $0.5$ charges from $b_{11}$.

  3. $C$:

Since $x_{11}\in V_{24}$, $|\\{x_{3},x_{4}\\}\cap V_{13}|\leq 1$. Thus
$g^{\prime}(x_{i})\geq 0$ for some $i\in\\{3,4\\}$. Since
$g^{\prime}(b_{11})\geq 0.5$ and $g^{\prime}(x_{11})\geq 0.5$,
$g^{*}(x_{2})\geq 0$ by taking $0.5$ charges from $b_{11}$.

  4. $D$:

Since $\\{a_{2},x_{2},x_{3},b_{1}\\}\subseteq N(b_{11})$ and $a_{2}x_{3}\notin
E(G)$, $d(b_{11})\geq 5$ and $g^{\prime}(b_{11})\geq 1$. Thus
$g^{*}(x_{2})\geq 0$ by taking $0.5$ charges from $b_{11}$.

  5. $E$:

Since $g^{\prime}(b_{11})\geq 1$, $g^{*}(x_{2})\geq 0$ by taking $0.5$ charges
from $b_{11}$.

  6. $F$:

Since $\\{x_{2},a_{1},b_{11}\\}\subseteq N(y_{11})$ and $x_{2}\in V_{34}\cup
V_{24}$, $d(y_{11})\geq 5$ and $g^{\prime}(y_{11})\geq 1$. Thus
$g^{*}(x_{2})\geq 0$ by taking $0.5$ charges from $y_{21}$.

  7. $G$:

If $b_{11}x_{11}\in E(G)$, then $g^{*}(x_{2})\geq 0$ by taking $0.5$ charges
from $b_{11}$. If $b_{11}x_{11}\notin E(G)$, then $x_{2}x_{11}\in E(G)$ and
$x_{2}\in V_{34}$. Since $b_{1}a_{3}\notin E(G)$, we consider the cases of
$K_{2,2}$ between $N(b_{1})$ and $N(a_{3})$. Let $\\{y_{31},y_{32}\\}\subseteq
N(a_{1})\cap V_{3}$ if they exists. if $\\{x_{11},x_{2}\\}\sim\\{*,y_{31}\\}$,
then $g^{*}(x_{2})\geq 0$ by taking $0.5$ charges from $y_{31}$. If
$\\{*,b_{11}\\}\sim\\{*,y_{31}\\}$, then $g^{*}(x_{2})\geq 0$ by taking $0.5$
charges from $b_{11}$.

In each case, we let $b_{1}$ sent $0.5$ charges to $x_{1}$. Thus
$g^{*}(x_{1})\geq 0$.

Now we consider the case when $b_{1}x_{11}\notin E(G)$ and $b_{1}a_{3}\in
E(G)$. If $d(b_{1})\geq 5$ or there exists $x_{2}\in N(b_{1})\cap V_{2}$ with
$g^{\prime}(x_{2})\geq 0$ when $d(b_{1})=4$ , then $g^{*}(x_{1})\geq 0$ by
taking $0.5$ charges from $b_{1}$. So we assume that $d(b_{1})=4$ and
$N(b_{1})\cap V^{\prime}_{2}=N(b_{1})\cap V_{2}$. Let
$N(b_{1})=\\{a_{3},x_{1},x_{2},b_{11}\\}$ or
$N(b_{1})=\\{a_{3},x_{1},x_{2},x_{21}\\}$. In the former case, we have
$b_{11}x_{2}\in E(G)$. Since $a_{1}b_{1}\notin E(G)$, we consider the cases of
$K_{2,2}$ between $N(b_{1})$ and $N(a_{1})$. Let $\\{x_{3},x_{4}\\}\subseteq
N(a_{1})\cap V_{2}$ and $\\{y_{11},y_{12}\\}\subseteq N(a_{1})\cap V_{3}$ if
they exists. If $\\{a_{2},*\\}\sim\\{*,b_{11}\\}$, then $x_{2}\in V_{34}$ and
$|N(b_{11})\cap V_{2}|\geq 2$. Let $x_{3}\in N(b_{11})\cap
V_{2}\setminus\\{x_{2}\\}$ and $x_{3}\in V_{13}\cup V_{34}$. Since there is no
edge in $\\{a_{2},x_{3},x_{2}\\}$, $d(b_{11})\geq 5$ and $g^{*}(x_{2})\geq 0$
by taking $0.5$ charges from $b_{11}$. If
$\\{*,x_{2}\\}\sim\\{y_{11},y_{12}\\}$, then $g^{*}(x_{2})\geq 0$ by taking
$0.25$ charges from $y_{1i}$, where $i\in[2]$. If
$\\{a_{3},b_{11}\\}\sim\\{x_{3},x_{4}\\}$, then $g^{\prime}(x_{i})\geq 0$ for
$i\in\\{3,4\\}$ when $d(b_{11})=4$ and $g^{\prime}(b_{11})\geq 1.5$ when
$d(b_{11})\geq 6$. Thus $g^{*}(x_{2})\geq 0$ by taking $0.5$ charges from
$b_{11}$. When $d(b_{11})=5$ and $\\{x_{2},x_{3},x_{4}\\}\subseteq
V^{\prime}_{2}$, if $b_{11}a_{3}\in E(G)$ or $b_{11}a_{1}\in E(G)$, then
$g^{\prime}(b_{11})\geq 1.5$ and $g^{*}(x_{2})\geq 0$ by taking $0.5$ charges
from $b_{11}$. If $b_{11}a_{3}\notin E(G)$, then $x_{2}a_{3}\in E(G)$ and
$x_{2}\in V_{34}$. Let $N(b_{11})=\\{x_{2},x_{3},x_{4},b_{1},b_{111}\\}$. If
$b_{11}a_{1}\notin E(G)$, then there must be
$\\{x_{j},*\\}\sim\\{y_{11},y_{12}\\}$, where $j\in\\{2,3,4\\}$ and
$\\{y_{11},y_{12}\\}\subseteq N(a_{1})\cap V_{3}$. Thus $g^{*}(x_{2})\geq 0$
by taking $0.5$ charges from $b_{11}$. Similarly, we have $g^{*}(x_{1})\geq 0$
by taking $0.5$ charges from $b_{1}$ in each case.

In the latter case, we have $x_{2}x_{21}\in E(G)$. Since $x_{2},x_{21}\in
V^{\prime}_{2}$, $x_{2}\in V_{24}$ and $x_{21}\in V_{13}$. Since
$b_{1}a_{2}\notin E(G)$, we have
$\\{x_{2},*\\}(\text{or}\\{x_{21},*\\})\sim\\{y_{21},y_{22}\\}$. Thus
$g^{*}(x)\geq 0$ for $x\in N(b_{1})\cap V_{2}$ by taking $1$ charges from
$b_{1}$ and $0.25$ charges from $y_{2i}$, where $i\in[2]$.

For $x_{1}\in V^{\prime}_{2}\cap V_{34}$, we consider $d(x_{1})\geq 5$ and
there exists $z_{1}\in N(x_{1})\cap V_{4}$ such that $g^{\prime}(z_{1})=0$.
Let $N(z_{1})=\\{x_{1},x_{2},z_{11},z_{12}\\}$ and $z_{11}x_{i}\in E(G)$ for
some $i\in[2]$. Note that $\\{a_{3},a_{4}\\}\subseteq N(x_{2})\cap V_{1}$.
Since $z_{1}a_{1}\notin E(G)$, we consider the cases of $K_{2,2}$ between
$N(z_{1})$ and $N(a_{1})$ as shown in Table 5. Let $\\{x_{3},x_{4}\\}\subseteq
N(a_{1})\cap V_{2}$ and $\\{y_{11},y_{12}\\}\subseteq N(a_{1})\cap V_{3}$ if
they exist.

Table 5: The cases of $K_{2,2}$ between $N(z_{1})$ and $N(a_{1})$. Here
$\times$ means that the case is impossible.

$z_{1}$ $a_{1}$ | $\\{a_{2},x_{3}\\}$ | $\\{a_{2},y_{11}\\}$ | $\\{x_{3},x_{4}\\}$ | $\\{x_{3},y_{11}\\}$ | $\\{y_{11},y_{12}\\}$
---|---|---|---|---|---
$\\{x_{1},x_{2}\\}$ | $\times$ | $\times$ | $\times$ | $\times$ | $A$
$\\{x_{1},z_{11}\\}$ | $\times$ | $\times$ | $\times$ | $\times$ | $A$
$\\{x_{2},z_{11}\\}$ | $B$ | $B$ | $C$ | $D$ | $D$
$\\{z_{11},z_{12}\\}$ | $D$ | $D$ | $D$ | $D$ | $D$

  1. $A$:

Since $g^{\prime}(y_{1i})>0$ for $i\in[2]$, $g^{*}(x_{j})\geq 0$ for
$j\in[2]$.

  2. $B,C$:

In the case of $B$, we have $g^{\prime}(z_{11})\geq 0.5$,
$g^{\prime}(x_{3})\geq 0$ and $g^{\prime}(x_{2})\geq 0$. In the case of $C$,
we have $g^{\prime}(x_{j})\geq 0$ for $j\in\\{2,3,4\\}$. If $z_{11}x_{1}\in
E(G)$, then $g^{*}(x_{1})\geq 0$ by taking $0.5$ charges from $z_{11}$. If
$z_{11}x_{2}\in E(G)$, then $z_{11}$ can send $0.25$ charges to $z_{1}$. So
$g^{*}(x_{1})\geq 0$ by taking $0.25$ charges from $z_{1}$.

  3. $D$:

Since $z_{1}a_{3}\notin E(G)$, we consider the cases of $K_{2,2}$ between
$N(z_{1})$ and $N(a_{3})$ as shown in Table 6. Let $\\{x_{5},x_{6}\\}\subseteq
N(a_{1})\cap V_{2}$ and $\\{y_{31},y_{32}\\}\subseteq N(a_{1})\cap V_{3}$ if
they exist.

Table 6: The cases of $K_{2,2}$ between $N(z_{1})$ and $N(a_{3})$. Here
$\times$ means that the case is impossible.

$z_{1}$ $a_{3}$ | $\\{a_{2},x_{5}\\}$ | $\\{a_{2},y_{31}\\}$ | $\\{a_{4},x_{5}\\}$ | $\\{a_{4},y_{31}\\}$ | $\\{x_{5},x_{6}\\}$ | $\\{x_{5},y_{31}\\}$ | $\\{y_{31},y_{32}\\}$
---|---|---|---|---|---|---|---
$\\{x_{1},x_{2}\\}$ | $\times$ | $\times$ | $\times$ | $F$ | $\times$ | $\times$ | $E$
$\\{x_{1},z_{1i}\\}$ | $\times$ | $\times$ | $\times$ | $F$ | $\times$ | $\times$ | $E$
$\\{x_{2},z_{1i}\\}$ | $F$ | $F$ | $F$ | $F$ | $F$ | $F$ | $F$
$\\{z_{11},z_{12}\\}$ | $F$ | $F$ | $F$ | $F$ | $F$ | $F$ | $F$

  1. $E$:

Since $g^{\prime}(y_{31})\geq 0$, $g^{*}(x_{i})\geq 0$ for $i\in[2]$.

  2. $F$:

In each case of $D$, we have $g^{*}(x_{1})\geq 0$.

For $x_{1}\in V^{\prime}_{2}\cap V_{13}$, we have $d(x_{1})\geq 5$ since there
is no edge in $\\{a_{1},a_{3},x_{11}\\}$. By Claim 10, we may assume that
there exists $b_{1}\in N(x_{1})\cap(V_{3}\cup V_{4})$ with
$g^{\prime}(b_{1})=0$. If $b_{1}\in V_{3}$, then
$N(b_{1})=\\{a_{2},x_{1},b_{11},b_{12}\\}$, where
$\\{b_{11},b_{12}\\}=N(b_{1})\cap(V_{3}\cup V_{4})$. If $|V^{\prime}_{13}|\geq
1$, then there exists $x_{2}\in V_{24}\setminus\\{x_{11}\\}$ by Case 1. Since
$b_{1}x_{2}\notin E(G)$, we consider the cases of $K_{2,2}$ between $N(b_{1})$
and $N(x_{2})$ as shown in Table 7. Let $\\{x_{3},x_{4}\\}\subseteq
N(x_{2})\cap V_{2}$ and $\\{b_{3},b_{4}\\}\subseteq N(x_{2})\cap(V_{3}\cup
V_{4})$ if they exist.

Table 7: The cases of $K_{2,2}$ between $N(b_{1})$ and $N(x_{2})$

$b_{1}$ $x_{2}$ | $\\{a_{2},x_{3}\\}$ | $\\{a_{2},b_{3}\\}$ | $\\{a_{4},x_{3}\\}$ | $\\{a_{4},b_{3}\\}$ | $\\{x_{3},x_{4}\\}$ | $\\{x_{3},b_{3}\\}$ | $\\{b_{3},b_{4}\\}$
---|---|---|---|---|---|---|---
$\\{x_{1},a_{2}\\}$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | $A$ | $B$
$\\{a_{2},b_{11}\\}$ | $\times$ | $\times$ | $\times$ | $\times$ | $C$ | $C$ | $C$
$\\{x_{1},b_{11}\\}$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | $C$ | $B$
$\\{b_{11},b_{12}\\}$ | $C$ | $C$ | $C$ | $C$ | $C$ | $C$ | $C$

  1. $A$:

Since $g^{\prime}(b_{3})\geq 0.5$ and $g^{\prime}(x_{2})\geq 0$,
$g^{*}(x_{1})\geq 0$ by taking $0.5$ charges from $b_{3}$.

  2. $B$:

Since $g^{\prime}(b_{3})\geq 0.5$ and $g^{\prime}(b_{4})\geq 0.5$,
$g^{*}(x_{1})\geq 0$ by taking $0.25$ charges from $b_{i}$ for
$i\in\\{3,4\\}$.

  3. $C$:

Since $b_{1}a_{1}\notin E(G)$, we consider the cases of $K_{2,2}$ between
$N(b_{1})$ and $N(a_{1})$ as shown in Table 8. Let $\\{x_{3},x_{4}\\}\subseteq
N(x_{2})\cap V_{2}$ and $\\{b_{3},b_{4}\\}\subseteq N(a_{1})\cap(V_{3}\cup
V_{4})$ if they exist.

    1. $C_{1}$:

Since $g^{\prime}(b_{3})\geq 0.5$ and $g^{\prime}(b_{4})\geq 0.5$, then
$g^{*}(x_{1})\geq 0$.

    2. $C_{2}$:

When each $C$ and $C_{2}$ occur together, we have $g^{*}(x_{1})\geq 0$.

Table 8: The cases of $K_{2,2}$ between $N(b_{1})$ and $N(a_{1})$

$b_{1}$ $a_{1}$ | $\\{a_{2},x_{3}\\}$ | $\\{a_{2},b_{3}\\}$ | $\\{x_{3},b_{3}\\}$ | $\\{b_{3},b_{4}\\}$
---|---|---|---|---
$\\{x_{1},a_{2}\\}$ | $\times$ | $\times$ | $\times$ | $\times$
$\\{a_{2},b_{11}\\}$ | $\times$ | $\times$ | $\times$ | $\times$
$\\{x_{1},b_{11}\\}$ | $\times$ | $\times$ | $\times$ | $C_{1}$
$\\{b_{11},b_{12}\\}$ | $C_{2}$ | $C_{2}$ | $C_{2}$ | $C_{2}$

When $b_{1}\in V_{4}$, let $N(b_{1})=\\{x_{1},x_{2},b_{11},b_{12}\\}$, where
$\\{a_{1},a_{3}\\}\subseteq N(x_{2})\cap V_{1}$ and
$\\{b_{11},b_{12}\\}=N(b_{1})\cap(V_{3}\cup V_{4})$. Since $G[N(b_{1})]\neq
K_{1,3}$ and $e(G[N(b_{1})])\geq 3$, $b_{11}x_{i}\in E(G)$ and $b_{12}x_{i}\in
E(G)$ for $i,j\in[2]$. Since $b_{1}a_{4}\notin E(G)$, we consider the cases of
$K_{2,2}$ between $N(b_{1})$ and $N(a_{4})$ as shown in Table 9. Let
$\\{x_{3},x_{4}\\}\subseteq N(a_{4})\cap V_{2}$ and
$\\{y_{41},y_{42}\\}\subseteq N(a_{4})\cap(V_{3}\cup V_{4})$ if they exist.

Table 9: The cases of $K_{2,2}$ between $N(b_{1})$ and $N(a_{4})$

$b_{1}$ $a_{4}$ | $\\{a_{3},x_{3}\\}$ | $\\{a_{3},y_{41}\\}$ | $\\{x_{3},x_{4}\\}$ | $\\{x_{3},y_{41}\\}$ | $\\{y_{41},y_{42}\\}$
---|---|---|---|---|---
$\\{x_{1},x_{2}\\}$ | $\times$ | $A$ | $\times$ | $\times$ | $B$
$\\{x_{1},b_{11}\\}$ | $C$ | $A$ | $\times$ | $A$ | $B$
$\\{x_{2},b_{11}\\}$ | $C$ | $\times$ | $D$ | $C$ | $C$
$\\{b_{11},b_{12}\\}$ | $C$ | $C$ | $C$ | $C$ | $C$

  1. $A$:

In this case, we have $\\{a_{4},x_{1},x_{i}\\}\subseteq N(y_{41})$, where
$\\{a_{1},a_{3}\\}\subseteq N(x_{i})\cap V_{1}$. If $x_{i}a_{4}\in E(G)$, then
$g^{\prime}(x_{i})\geq 0$ and $g^{*}(x_{1})\geq 0$ by taking $0.5$ charges
from $y_{41}$. If $x_{2}a_{4}\notin E(G)$, there is no edges in
$\\{a_{4},x_{1},x_{2}\\}$, then $d(y_{41})\geq 5$, $g^{\prime}(y_{41})\geq 1$
and $g^{*}(x_{1})\geq 0$.

  2. $B$:

Since $g^{\prime}(y_{4i})\geq 0.5$ for $i\in[2]$, $g^{*}(x_{1})\geq 0$ and
$g^{*}(x_{2})\geq 0$.

  3. $C$:

If $\\{x_{1},x_{2}\\}\subseteq N(b_{11})\cap N(b_{12})$, then we have
$g^{*}(x_{i})\geq 0$ for $i\in[2]$ When $\\{x_{1},x_{2}\\}\nsubseteq
N(b_{11})\cap N(b_{12})$, since $b_{1}a_{1}\notin E(G)$, we consider the cases
of $K_{2,2}$ between $N(b_{1})$ and $N(a_{1})$ as shown in Table 10. Let
$\\{x_{5},x_{6}\\}\subseteq N(a_{1})\cap V_{2}$ and
$\\{y_{11},y_{12}\\}\subseteq N(a_{1})\cap(V_{3}\cup V_{4})$ if they exist.

    1. $E$:

We have $g^{*}(x_{1})\geq 0$ for each $C$ and $E$.

    2. $F$:

Since $g^{\prime}(y_{1j})\geq 0.5$ for $j\in[2]$, $g^{*}(x_{1})\geq 0$ and
$g^{*}(x_{2})\geq 0$.

  4. $D$:

Since $x_{3}x_{2}\in E(G)$ and $x_{2}x_{4}\in E(G)$, $g^{\prime}(x_{2})\geq
0$. If $x_{3}\in V^{\prime}_{2}$, then $x_{3}\in V_{24}$ and $x_{4}\notin
V_{24}$ by Case 1. Thus there exists $x_{i}$ for $i\in\\{3,4\\}$ such that
$g^{\prime}(x_{i})\geq 0$. Since there is no edge in
$\\{x_{3},x_{4},b_{1}\\}$, $d(b_{11})\geq 5$ and $g^{\prime}(b_{11})\geq 1$.
Thus if $b_{11}x_{1}\in E(G)$, then $g^{*}(x_{1})\geq 0$ by taking $0.5$
charges from $b_{11}$; if $b_{11}x_{2}\in E(G)$, then $b_{11}$ can send $0.5$
charges to $b_{1}$ and $g^{*}(x_{1})\geq 0$ by taking $0.5$ charges from
$b_{11}$.

Table 10: The cases of $K_{2,2}$ between $N(b_{1})$ and $N(a_{1})$

$b_{1}$ $a_{1}$ | $\\{a_{2},x_{5}\\}$ | $\\{a_{2},y_{11}\\}$ | $\\{x_{5},x_{6}\\}$ | $\\{x_{5},y_{11}\\}$ | $\\{y_{11},y_{12}\\}$
---|---|---|---|---|---
$\\{x_{1},x_{2}\\}$ | $\times$ | $\times$ | $\times$ | $\times$ | $F$
$\\{x_{1},b_{11}\\}$ | $\times$ | $\times$ | $\times$ | $\times$ | $E$
$\\{x_{2},b_{11}\\}$ | $E$ | $E$ | $E$ | $E$ | $E$
$\\{b_{11},b_{12}\\}$ | $E$ | $E$ | $E$ | $E$ | $E$

###### Claim 11

When $G[V_{1}\setminus\\{a\\}]=C_{3}\cup K_{1}$ and $C_{3}=a_{1}a_{2}a_{3}$.

_Proof._ For any $x_{1}\in V^{\prime}_{2}$, if $b_{1}\in
N(x_{1})\cap(V_{3}\cup V_{4})$ with $g^{\prime}(b_{1})\geq 0.5$, then $b_{1}$
can send at least $0.25$ charges to $x_{1}$ except $b_{1}\in V_{4}$ and
$N(b_{1})=\\{x_{1},x_{2},x_{21},b_{11}\\}$, where $x_{1},x_{2}\in V_{12}$,
$x_{21}\in V_{23}\cup V_{13}$ and $\\{x_{2},x_{21},b_{11}\\}$ is a cycle. We
consider such a special vertex $b_{1}$. Since $b_{1}a_{4}\notin E(G)$ and the
case of $K_{2,2}$ between $b_{1}$ and $a_{4}$ can only be
$\\{x,b_{11}\\}\sim\\{y_{31},y_{31}\\}$, where $x\in\\{x_{1},x_{2},x_{21}\\}$,
$g^{\prime}(b_{11})\geq 1.5$, $g^{*}(x_{2})\geq 0$ and $g^{*}(x_{11})\geq 0$.
Thus $g^{*}(x_{1})\geq 0$. For any $x_{1}\in V^{\prime}_{12}$, we have
$x_{11}\in V_{23}\cup V_{13}$. When $d(x_{1})=4$ and $x_{11}\in V_{23}$, let
$N(x_{1})=\\{a_{1},a_{2},x_{11},b_{1}\\}$, since $a_{1}x_{2}\notin E(G)$,
$\\{a_{2},x_{11},b_{1}\\}$ induces a cycle. If $d(b_{1})\geq 5$, then
$|N(b_{1})\cap V_{2}|\geq 3$ and $g^{\prime}(b_{1})\geq 1.5$. Thus
$g^{*}(x_{1})\geq 0$. When $d(b_{1})=4$, let
$N(b_{1})=\\{a_{2},x_{11},x_{1},x_{2}\\}$ where $x_{2}\in V_{12}\cup V_{23}$.
We may assume that $\\{x_{1},x_{2},x_{11}\\}\subseteq V^{\prime}_{2}$
otherwise we are done. Since $b_{1}a_{4}\notin E(G)$ and the case of $K_{2,2}$
between $b_{1}$ and $a_{4}$ can only be
$\\{x_{i},x_{j}\\}\sim\\{y_{41},y_{42}\\}$, where
$\\{x_{i},x_{j}\\}\subseteq\\{x_{1},x_{2},x_{11}\\}$ and
$\\{y_{41},y_{42}\\}\subseteq N(a_{4})\cap V_{4}$, $g^{*}(x_{1})\geq 0$.

Next we consider $x_{1}\in V^{\prime}_{12}$ with $d(x_{1})\geq 5$. If $x_{1}$
has at least two positive neighbors, then $g^{*}(x_{1})\geq 0$. Otherwise,
there exists $b_{1}\in N(x_{1})\cap(V_{3}\cup V_{4})$ with
$g^{\prime}(b_{1})=0$. When $b_{1}\in V_{3}$, let
$N(b_{1})=\\{a_{3},x_{1},b_{11},b_{12}\\}$, where
$\\{b_{11},b_{12}\\}\subseteq N(b_{1})\cap(V_{3}\cup V_{4})$ and either
$\\{x_{1},b_{11},b_{12}\\}$ or $\\{a_{3},b_{11},b_{12}\\}$ induces a cycle.
Since $b_{1}a_{4}\notin E(G)$, we consider the cases of $K_{2,2}$ between
$b_{1}$ and $a_{4}$. Suppose that $\\{*,b_{11}\\}\sim\\{x_{4},x_{5}\\}$. If
$\\{x_{1},b_{11},b_{12}\\}$ induces a cycle, then $g^{\prime}(b_{1i})\geq 1$
for $i\in[2]$. Thus $g^{*}(x_{1})\geq 0$. If $\\{a_{3},b_{11},b_{12}\\}$
induces a cycle, then $g^{\prime}(b_{1i})\geq 1$for $i\in[2]$ and $b_{1i}$ can
send $0.25$ charges to $x_{4}$ and $x_{5}$, respectively. Thus
$g^{*}(x_{4})\geq 0$ and $g^{*}(x_{5})\geq 0$. Hence, $b_{11}$ can send $0.5$
charges to $b_{1}$ and $g^{*}(x_{1})\geq 0$. Suppose that
$\\{x_{1},b_{11}\\}\sim\\{y_{4},y_{5}\\}$. Since $g^{\prime}(y_{4})\geq 0$ and
$g^{\prime}(y_{5})\geq 0$, $g^{*}(x_{1})\geq 0$. Suppose that
$\\{b_{11},b_{12}\\}\sim\\{x_{4},y_{4}\\}$. If $\\{x_{1},b_{11},b_{12}\\}$
induces a cycle, then ${}^{\prime}(b_{1i})\geq 0.5$ for $i\in[2]$. Thus
$g^{*}(x_{1})\geq 0$. If $\\{a_{3},b_{11},b_{12}\\}$ induces a cycle, then
$g^{\prime}(b_{1i})\geq 0.5$ and the equality holds when $|N(b_{1i})\cap
V_{2}|=1$ . Thus $b_{11}$ can send $0.5$ charges to $b_{1}$ and
$g^{*}(x_{1})\geq 0$. Suppose that $\\{b_{11},b_{12}\\}\sim\\{y_{4},y_{5}\\}$.
If $\\{x_{1},b_{11},b_{12}\\}$ induces a cycle, then $g^{\prime}(b_{1i})\geq
0.5$ for $i\in[2]$. Thus $g^{*}(x_{1})\geq 0$. If $\\{a_{3},b_{11},b_{12}\\}$
induces a cycle, then $b_{11}$ can send $0.5$ charges to $b_{1}$ since
$|N(b_{11})\cap V_{3}|\geq 4$. Thus $g^{*}(x_{1})\geq 0$.

When $b_{1}\in V_{4}$, let $N(b_{1})=\\{x_{1},x_{2},b_{11},b_{12}\\}$ where
$\\{x_{1},x_{2}\\}\subseteq V_{12}$, then either $\\{x_{1},b_{11},b_{12}\\}$
or $\\{x_{2},b_{11},b_{12}\\}$ is a cycle. Since $b_{1}a_{4}\notin E(G)$, if
$\\{x_{1},x_{2}\\}\sim\\{y_{41},y_{42}\\}$, then $g^{*}(x_{i})\geq 0$,
$i\in[2]$. If $\\{x_{1}(x_{2}),b_{11}\\}\sim\\{y_{41},y_{42}\\}$, then
$g^{*}(x_{1})\geq 0$, when $b_{11}x_{2}\in E(G)$, then $g^{*}(x_{2})\geq 0$;
when $b_{11}x_{2}\notin E(G)$, then $\\{b_{11},b_{12},x_{1}\\}$ is a $K_{3}$
and $g^{\prime}(b_{11})\geq 1$ and $b_{11}$ can send $0.5$ to $b_{1}$, thus
$g^{*}(x_{2})\geq 0$. If $\\{x_{2},b_{11}\\}\sim\\{x_{3},y_{41}\\}$, then
$g^{\prime}(x_{2})\geq 0$, $g^{\prime}(b_{11})\geq 1$ and if $x_{1}b_{11}\in
E(G)$, then $g^{*}(x_{1})\geq 0$; if $x_{2}b_{11}\in E(G)$, then $b_{11}$ can
send $0.5$ charges to $b_{1}$, thus $g^{*}(x_{1})\geq 0$. If
$\\{x_{2},b_{11}\\}\sim\\{x_{3},x_{4}\\}$, since $b_{1}a_{1}\notin E(G)$, when
$\\{b_{11},x_{2}\\}\sim\\{x_{5},x_{6}\\}$, if
$\\{x_{3},x_{4}\\}=\\{x_{5},x_{6}\\}$, then $g^{\prime}(x_{j})\geq 0$,
$j\in\\{3,4\\}$ and $b_{11}$ can send $0.5$ charges to $b_{1}$, thus
$g^{*}(x_{1})\geq 0$; if $\\{x_{3},x_{4}\\}\neq\\{x_{5},x_{6}\\}$, then
$g^{\prime}(b_{11})\geq 2$ and $g^{*}(x_{1})\geq 0$. When
$\\{*,b_{11}\\}\sim\\{y_{11},*\\}$, then $g^{\prime}(b_{11})\geq 1.5$, then
$g^{*}(x_{1})\geq 0$. If $\\{b_{11},b_{12}\\}\sim\\{*,y_{41}\\}$, then
$g^{\prime}(b_{1i})\geq 0.5$, $i\in[2]$ and $g^{*}(x_{i})\geq 0$, $i\in[2]$.
If $\\{b_{11},b_{12}\\}\sim\\{x_{3},x_{4}\\}$, if
$x_{2}\notin\\{x_{3},x_{4}\\}$, then $g^{*}(x_{i})\geq 0$, $i\in[2]$. If
$x_{2}\in\\{x_{3},x_{4}\\}$, sicne $b_{1}a_{1},b_{1}a_{2}\notin E(G)$, when
$\\{x_{1},*\\}\sim\\{y_{41},y_{42}\\}$, then $g^{*}(x_{1})\geq 0$; when
$\\{b_{11},*\\}\sim\\{x_{1},*\\}$, then $g^{*}(x_{1})\geq 0$.

Since $e(V_{1})\geq 7$, we need to prove $w_{2}+w_{3}+w_{4}\geq-1.5$. For
$x_{1}\in V^{\prime}_{i4}$, $i\in[3]$, if there are two positive neighbors of
$x_{1}$, then $g^{*}(x_{1})\geq 0$. Otherwise, there exists $z_{1}\in
N(x_{1})\cap V_{4}$ with $g^{\prime}(z_{1})=0$. Then we consider there are at
least four such vertices. Let $N(z_{1})=\\{x_{1},x_{2},z_{11},z_{12}\\}$.
There exists $x_{3}\in V_{kj}$, $k,j\in[3]$ and $x_{31}\in N(x_{3})\cap
V^{\prime}_{i4}$, $i\in[2]$. We can choose $x_{3}$ such that $x_{3}\notin
N(x_{1})$. Since $z_{1}x_{3}\notin E(G)$, when
$\\{x_{1},x_{2}\\}\sim\\{*,b_{31}\\}$, $i\in[3]$ where $b_{31}\in
N(x_{3})\cap(V_{3}\cup V_{4})$, because $d(b_{31})\neq 4$,
$g^{\prime}(b_{31})\geq 1$ and $g^{\prime}(x_{3})\geq 0$, thus
$g^{*}(x_{1})\geq 0$ and $g^{*}(x_{2})\geq 0$. When
$\\{x_{2},z_{11}\\}\sim\\{a_{i},x_{31}\\}$,
$\\{a_{i},x_{t},x_{31},z_{12}\\}\subseteq N(z_{11})$, $t\in[2]$, then
$d(z_{11})\geq 5$, $g^{\prime}(z_{11})\geq 1$ and $z_{11}$ can send $0.5$
charges to $z_{1}$, thus $g^{*}(x_{t})\geq 0$, $t\in[2]$. When
$\\{x_{2},z_{11}\\}\sim\\{a_{i},b_{31}\\}$, then $|N(z_{11})\cap V_{2}|\geq
2$, $g^{\prime}(z_{11})\geq 1$ and $\\{x_{2},z_{11},x_{3}\\}\subseteq
N(b_{31})$, if $d(b_{31})=4$ or $d(b_{31})\geq 5$, we have $g^{*}(x_{1})\geq
0$ and $g^{*}(x_{2})\geq 0$. When
$\\{z_{11},z_{12}\\}\sim\\{b_{31},b_{32}\\}$, then $g^{\prime}(b_{1i})\geq 1$,
$i\in[2]$ and $g^{*}(x_{i})\geq 0$, $i\in[2]$. When
$\\{z_{11},z_{12}\\}\sim\\{x_{2},x_{31}\\}$, then we choose $x_{3}=x_{11}$.
When $\\{z_{11},z_{12}\\}\sim\\{b_{31},x_{31}\\}$, then
$g^{\prime}(z_{1i})\geq 0.5$, $i\in[2]$ and we can choose $x_{4}$, thus
$g^{*}(x_{i})\geq 0$, $i\in[2]$.

###### Claim 12

When
$E(G[V_{1}\setminus\\{a\\}])=\\{a_{1}a_{2},a_{2}a_{3},a_{3}a_{4},a_{1}a_{3}\\}$,
$w^{\prime}_{2}+w^{\prime}_{3}+w^{\prime}_{4}\geq-2.5$.

_Proof._ By symmetry, we only need to consider the vertices in
$V^{\prime}_{2}\cap(V_{12}\cup V_{13}\cup V_{14}\cup V_{34})$. For any
$b_{1}\in N(x_{1})\cap(V_{3}\cup V_{4})$ where $x_{1}\in V^{\prime}_{2}$, if
$g^{\prime}(b_{1})\geq 0.5$, then $b_{1}$ can send at least $0.25$ charges to
$x_{1}$ except $N(b_{1})=\\{x_{1},x_{2},x_{21},b_{11}\\}$, where
$\\{x_{1},x_{2},x_{21}\\}\subseteq V^{\prime}_{2}$ and $b_{11}\in
N(x_{1})\cap(V_{3}\cup V_{4})$. Since $e(G[N(b_{1})])\geq 4$,
$\\{x_{1},x_{2},x_{21}\\}\subseteq N(b_{11})$. Since $b_{1}a_{4}\notin E(G)$,
we consider the cases of $K_{2,2}$ between $b_{1}$ and $a_{4}$. If
$\\{*,b_{11}\\}\sim\\{a_{3},*\\}$, then $g^{\prime}(b_{11})\geq 1.5$ and
$g^{*}(x)\geq 0$ for any $x\in\\{x_{1},x_{2},x_{21}\\}$. If
$\\{x_{1},b_{11}\\}\sim\\{*,y_{41}\\}$ where $y_{41}\in(N(x_{1})\cap V_{3})$,
$g^{\prime}(b_{11})\geq 1$ when $d(y_{41})=4$, $|N(y_{41})\cap
V^{\prime}_{2}|\leq 1$, then $g^{*}(x)\geq 0$, $x\in\\{x_{1},x_{2},x_{21}\\}$;
when $d(y_{41})\geq 5$, $g^{\prime}(y_{41})\geq 1$, then $g^{*}(x)\geq 0$,
$x\in\\{x_{1},x_{2},x_{21}\\}$. If $\\{x_{1},x_{2}\\}\sim\\{y_{41},y_{42}\\}$
or $\\{x_{1},x_{21}\\}\sim\\{y_{41},y_{42}\\}$ or
$\\{x_{2},x_{21}\\}\sim\\{y_{41},y_{42}\\}$, then $g^{*}(x)\geq 0$ for any
$x\in\\{x_{1},x_{2},x_{21}\\}$.

When $d(x_{1})=4$, let $N(x_{1})=\\{a_{i},a_{j},x_{11},b_{1}\\}$. Since
$e(G[N(x_{1})])\geq 4$, $\\{a_{j},x_{11},b_{1}\\}\subseteq N(a_{i})$ for some
$i\in[2]$ and when $x_{11}\in V^{\prime}_{2}$, $a_{i}\neq a_{4}$. If
$d(b_{1})\geq 5$, then $g^{\prime}(b_{1})\geq 1$ and $g^{*}(x_{1})\geq 0$.
When $d(b_{1})=4$, let $N(b_{1})=\\{a_{i},x_{11},x_{1},b_{11}\\}$ or
$N(b_{1})=\\{a_{i},x_{11},x_{1},x_{2}\\}$. assume that $N(b_{1})\cap
V_{2}=N(b_{1})\cap V^{\prime}_{2}$. (Otherwise, $g^{*}(x_{1})\geq 0$.) Since
$b_{1}a_{4}\notin E(G)$, we consider the cases of $K_{2,2}$ between $b_{1}$
and $a_{4}$. If $\\{*,x\\}\sim\\{a_{41},a_{42}\\}$ where
$x\in\\{x_{1},x_{11},x_{2}\\}$ and $\\{a_{41},a_{42}\\}\subseteq
N(a_{4})\cap(V_{2}\cup V_{3})$, then $g^{*}(x)\geq 0$ and $g^{*}(x_{1})\geq
0$. If $\\{a_{i},b_{11}\\}\sim\\{a_{41},a_{42}\\}$ and
$N(b_{1})=\\{a_{1},x_{11},x_{1},b_{11}\\}$, then $b_{11}a_{1}\in E(G)$,
$b_{11}x_{11}\in E(G)$, $g^{\prime}(b_{11})\geq 1.5$ and $g^{*}(x_{11})\geq
0$. Thus $g^{*}(x_{1})\geq 0$.

When $d(x_{1})\geq 5$, if $x_{1}$ has two positive neighbors, then
$g^{*}(x_{1})\geq 0$. Otherwise, there exists $b_{1}\in N(x_{1})\cap(V_{3}\cup
V_{4})$ with $g^{\prime}(b_{1})=0$. If $b_{1}\in V_{3}$, then
$N(b_{1})=\\{a_{k},x_{1},b_{11},b_{12}\\}$ and $e(G[N(b_{1})])\geq 4$. Thus
$\\{a_{k}b_{11},a_{k}b_{12},b_{11}b_{12},a_{k}x_{1}\\}\subseteq
E(G[N(b_{1})])$ or
$\\{x_{1}b_{11},x_{1}b_{12},b_{11}b_{12},a_{k}b_{11}\\}\subseteq
E(G[N(b_{1})])$ or
$\\{a_{k}b_{11},a_{k}b_{12},b_{11}x_{1},x_{1}b_{12}\\}\subseteq
E(G[N(b_{1})])$. Since $b_{1}a_{4}\notin E(G)$, we consider the cases of
$K_{2,2}$ between $b_{1}$ and $a_{4}$. If
$\\{x_{1},*\\}\sim\\{y_{41},y_{42}\\}$, then $g^{*}(x_{1})\geq 0$. If
$\\{b_{11},b_{12}\\}\sim\\{x_{4},x_{5}\\}$, then there exists $b_{11}$ such
that $\\{a_{k},x_{1},(x_{4}),x_{5},b_{1},b_{12}\\}\subseteq N(b_{11})$
($x_{1}\in\\{x_{4},x_{5}\\}$) or
$\\{a_{k},x_{1},(x_{4}),x_{5},b_{1}\\}\subseteq N(b_{1i})$, $i\in[2]$. Thus
$g^{*}(b_{11})\geq 1$ or $g^{\prime}(b_{1i})\geq 0.5$. Therefore,
$g^{*}(x_{1})\geq 0$. If $\\{b_{11},b_{12}\\}\sim\\{x_{4},y_{41}\\}$, when
$b_{11}b_{12}\in E(G)$, there exists $b_{11}$ such that
$\\{a_{k},x_{1},(x_{4}),y_{41},b_{1},b_{12}\\}\subseteq N(b_{1i})$
($x_{4}=x_{1}$), $i\in[2]$. then $g^{\prime}(b_{1i})\geq 0.5$ and
$g^{*}(x_{1})\geq 0$. When $b_{11}b_{12}\notin E(G)$, if $d(b_{1i})=4$, then
$y_{41}x_{1}\in E(G)$, $g^{\prime}(y_{41})\geq 1$ and $g^{*}(x_{1})\geq 0$. If
$\\{b_{11},b_{12}\\}\sim\\{y_{41},y_{42}\\}$, then there exists $b_{11}$ such
that $\\{a_{3},x_{1},y_{41},y_{42},b_{1}\\}\subseteq N(b_{11})$. Thus
$g^{*}(b_{11})\geq 0.5$ and $g^{*}(x_{1})\geq 0$.

If $\\{a_{k},b_{11}\\}\sim\\{a_{41},a_{42}\\}$ where $a_{41},a_{42}\in
N(a_{4})\cap V_{2}$, $x_{1}\notin\\{a_{41},a_{42}\\}$, when
$N(b_{11})=\\{a_{41},a_{42},x_{1},\\\ b_{12},b_{1}\\}$, we consider
$b_{11}a_{k}\notin E(G)$, if $\\{a_{41},a_{42}\\}\sim\\{y_{k1},*\\}$ where
$y_{k1}\in N(a_{k})\cap V_{3}$, then $g^{\prime}(y_{k1})\geq 0.5$, then
$g^{*}(x_{1})\geq 0$. If $\\{*,b_{12}\\}\sim\\{*,*\\}$, then
$g^{\prime}(b_{12})\geq 0.5$, then $g^{*}(x_{1})\geq 0$. If
$\\{x_{1},a_{41}\\}\sim\\{y_{41},*\\}$, then $g^{*}(x_{1})\geq 0$.

If $b_{1}\in V_{4}$, let $N(b_{1})=\\{x_{1},x_{2},b_{11},b_{12}\\}$ and
$e(G[N(b_{1})])\geq 4$, then
$\\{x_{1}b_{11},b_{11}b_{12},b_{12}x_{1},b_{11}x_{2}\\}\subseteq E(G)$ or
$\\{x_{2}b_{11},b_{11}b_{12},b_{12}x_{2},b_{11}x_{1}\\}\subseteq E(G)$ or
$\\{x_{1}b_{11},x_{1}b_{12},b_{12}x_{2},b_{11}x_{2}\\}\subseteq E(G)$. Denote
$A_{1}=V^{\prime}_{12}\cup V^{\prime}_{13}\cup V^{\prime}_{14}$ and
$A_{2}=V^{\prime}_{24}\cup V^{\prime}_{34}\cup V^{\prime}_{23}$. Then for any
$x_{1},x_{2}\in A_{i}$, $i\in[2]$, we have $x_{1}x_{2}\notin E(G)$. We may
assume that $|V^{\prime}_{2}|\geq 6$ and there exists $|A_{i}|\geq 3$, say
$A_{1}$. There is $x_{1}\in A_{1}$ with $z_{1}\in N(x_{1})\cap V_{4}$ and
$g^{\prime}(z_{1})=0$. Let $N(z_{1})=\\{x_{1},x_{2},z_{11},z_{12}\\}$ and
there exists $x_{3}\in A_{1}\setminus\\{x_{1},x_{2}\\}$ with $z_{2}\in
N(x_{3})\cap V_{4}$ and $g^{\prime}(z_{2})=0$. Let
$N(z_{2})=\\{x_{3},x_{4},z_{21},z_{22}\\}$. Since $z_{1}z_{2}\notin E(G)$,
when $\\{x_{1},x_{2}\\}\sim\\{z_{21},z_{22}\\}$, $g^{\prime}(z_{2i})\geq 1$,
$i\in[2]$ and $g^{*}(x_{j})\geq 0$, $j\in[4]$. When
$\\{x_{2},z_{11}\\}\sim\\{x_{4},z_{21}\\}$, $g^{\prime}(z_{11})\geq 0.5$ and
$g^{*}(x_{1})\geq 0$ and $g^{*}(x_{3})\geq 0$. When
$\\{x_{2},z_{11}\\}\sim\\{z_{21},z_{22}\\}$, $g^{\prime}(z_{11})\geq 0.5$ and
if $x_{2}\neq x_{4}$, then $N(x_{1})\cap V_{1}\neq N(x_{3})\cap V_{1}$,
$g^{\prime}(z_{2i})\geq 1$, $i\in[2]$, thus $g^{*}(x_{i})\geq 0$, $i\in[4]$;
if $x_{4}=x_{2}$, then there eixsts $x_{5}\in A_{1}$ with $z_{3}\in
N(x_{5})\cap V_{4}$ and $g^{\prime}(z_{3})=0$, we have $g^{\prime}(z_{12})\geq
0.5$ or $g^{\prime}(z_{11})\geq 1.5$, thus $g^{*}(x_{i})\geq 0$, $i\in[4]$.
When $\\{z_{11},z_{12}\\}\sim\\{z_{21},z_{22}\\}$, then
$g^{\prime}(z_{ij})\geq 0.5$, $i,j\in[2]$, thus $g^{*}(x_{k})\geq 0$,
$k\in[2]$.

###### Claim 13

When $G[V_{1}\setminus\\{a\\}]$ contains a copy of $K_{2,2}$, say
$\\{a_{1},a_{2}\\}\sim\\{a_{3},a_{4}\\}$,
$w^{\prime}_{2}+w^{\prime}_{3}+w^{\prime}_{4}\geq
1.5-e(G[V_{1}\setminus\\{a\\}])$.

_Proof._ Suppose that $e(G[V_{1}])=10$. By the choice of $a$, we have
$G[N(v)]$ is a copy of $K_{4}$ for any $d(v)=4$. We shall prove
$w^{\prime}_{2}+w^{\prime}_{3}+w^{\prime}_{4}\geq-4.5$. If $V_{2}=V_{ij}$,
assume that that $V_{2}=V_{12}$, then we require $|V^{\prime}_{2}|\geq 5$ with
the equality holds if and only if $x_{1}\in V^{\prime}_{2}$ and
$g^{\prime}(x_{1})=-1$. For any $x_{1}\in V^{\prime}_{2}$ and $y\in
N(x_{1})\cap V_{3}$, we have $d(y)\geq 5$ and
$g^{\prime}(y)\geq\max\\{|N(y)\cap V_{2}+2,3.5|\\}$. Let $x_{1}\in
V^{\prime}_{2}$ and $z\in N(x_{1})\cap V_{4}$. If $g^{\prime}(z)=0$, then
$x_{1}\in V_{2}^{-0.5}$ and $z\in N(x_{1})\cap N(x_{11})$, where $x_{11}\in
N(x_{1})\cap V_{2}$. Note that for any $x\in V_{2}^{-1}$, we have $d(z)\geq 5$
for any $z\in N(x)\cap V_{4}$. In the following, we redistribute the charges
of vertices. Let $g^{*}(v)$ denote the new charge of $v\in V(G)$.

(R1): For any $y\in V_{3}$, $y$ sends $0.5$ charges to each of its neighbors
in $V^{\prime}_{2}$.

(R2): For any $z\in V_{4}$ and $g^{\prime}(z)>0$, $z$ sends $0.25$ charges to
each of its neighbors in $V^{\prime}_{2}$.

Suppose that $N(x)\cap V_{3}\neq\emptyset$ for $x\in V^{\prime}_{2}$.
Obviously, $d(x)\geq 5$ and $g^{*}(x)\geq 0$ for any $x\in V^{-0.5}_{2}$ or
$x\in V^{-1}_{2}$ and $|N(x)\cap V_{3}|\geq 2$. If $|N(x)\cap V_{3}|=1$ for
$x\in V^{-1}_{2}$, then $d(x)\geq 5$ by the choice of $a$, and so
$g^{*}(x)\geq 0$. Since $g^{\prime}(y)\geq\max\\{|N(y)\cap V_{2}+2,3.5|\\}$
and $g^{\prime}(z)\geq|N(z)\cap V_{2}|+0.5|N(z)\cap V_{4}|$, $g^{*}(y)\geq 0$
and $g^{*}(z)\geq 0$.

Suppose that $N(x)\cap V_{3}=\emptyset$ for $x\in V^{\prime}_{2}$. Obviously,
we have $d(x)\geq 5$. Now we want to prove $g^{*}(x)\geq 0$ if $x\in
V^{-0.5}_{2}$. If there are at least two vertices $z\in N(x)\cap V_{4}$ such
that $g^{\prime}(z)\geq 0.5$, then $g^{*}(x)\geq 0$. Otherwise, let $z_{1}\in
N(x)$ with $g^{\prime}(z_{1})=0$, say $N(z_{1})=\\{x,x_{11},z_{11},z_{12}\\}$,
where $x_{11}\in z_{1}\cap V_{2}$ and $\\{z_{11},z_{12}\\}=z_{1}\cap V_{4}$.
Since $d(z_{1})=4$, $\\{z_{11},z_{12}\\}\subseteq N(x)$ and $N(x_{11})\cap
V_{1}=N(x)\cap V_{1}$, say $N(x)\in V_{12}$. We may assume that
$g^{\prime}(z_{11})=0$. For any $x^{\prime}\in V_{2}^{2}\setminus V_{12}$, we
have $x^{\prime}z_{1}\notin E(G)$. At this moment, the neighbors of $z_{1}$
that can be chosen to form $K_{2,2}$ are from $\\{x_{1},x_{11},z_{12}\\}$. If
$|V_{2}^{2}\setminus V_{12}|\geq 4$, then either there are two vertices $z\in
N(x)\cap V_{4}$ such that $g^{\prime}(z)\geq 0.5$ or there is a vertex
$z_{0}\in N(x)$ such that $g^{\prime}(z)$ can send $0.5$ charges to $x$. When
$|V_{2}^{2}\setminus V_{12}|\leq 3$ and $|V^{-0.5}_{2}|\geq 3$, assume that
$x_{1},x_{2}\in V^{-0.5}_{2}$ do not satisfy the conditions for $x$ in
$|V_{2}^{2}\setminus V_{12}|\geq 4$ and $x_{1}x_{2}\notin E(G)$. Let $z_{i}\in
N(x_{i})\cap V_{4}$ with $g^{\prime}(z_{i})=0$ and
$N(z_{i})=\\{x_{i},x_{i1},z_{i1},z_{i2}\\}$. Since $z_{1}z_{2}\notin E(G)$ and
the neighbors of $z_{i}$ that can be chosen to form $K_{2,2}$ are from
$\\{x_{i},x_{i1},z_{i2}\\}$. Thus $g^{*}(x_{i})\geq 0$. For any $x\in
V^{-1}_{2}$, we have $g^{\prime}(z)\geq 0.5$ if $z\in N(x)\cap V_{4}$ and $x$
can receive at least $0.75$ charges from its neighbors in $V_{4}$ since
$|N(x)\cap V_{4}|\geq 3$. When $|V_{2}^{2}\setminus V_{12}|\leq 3$ and
$|V^{-0.5}_{2}|\leq 2$, we only need to consider $|V^{-1}_{2}|\geq 9$. If
$|N(x)\cap V_{4}|\geq 4$, then $g^{*}(x)\geq 0$. If $|N(x)\cap V_{4}|=3$, then
there are $x_{i}\in(V^{-1}_{2}\cap V_{12})\backslash\\{x\\}$ such that
$x_{i}x\notin E(G)$, where $i\in[3]$. Thus there exists $z_{1}\in N(x)\cap
V_{4}$ such that it can send at least $0.5$ charges to $x$.

Assume that $e(V_{1})\leq 9$. For any $x_{1}\in V^{\prime}_{2}$, $b_{1}\in
N(x_{1})\cap(V_{3}\cup V_{4})$ with $g^{\prime}(b_{1})\geq 0.5$, then $b_{1}$
can send at least $0.25$ charges to $x_{1}$. When $b_{1}\in N(x_{1})\cap
V_{3}$ with with $g^{\prime}(b_{1})\geq 0.5$, if $b_{1}\in N(a_{1})$,
$x_{1}\in V_{34}\cap V^{-1}_{2}$, $\\{a_{1}\\}\sim\\{a_{3},a_{4}\\}$ and
$x_{1}a_{1}\notin E(G)$, then $b_{1}$ can send at least $0.5$ charges to
$x_{1}$.

We show that for any $x\in V^{\prime}_{2}$, if there exists $y_{1}\in N(x)\cap
V_{3}$ with $g^{\prime}(y_{1})=0$, then $g^{*}(x_{1})\geq 0$. Let
$N(y_{1})=\\{a_{3},x_{1},y_{11},y_{12}\\}$. Since $x_{1}a_{3}\notin E(G)$,
$\\{a_{3},x_{1}\\}\sim\\{y_{11},y_{12}\\}$. When there exists $x_{2}\in
V^{\prime}_{2}\setminus\\{x_{1}\\}$, $x_{1}x_{2}\notin E(G)$ and $y_{2}\in
N(x_{2})\cap V_{3}$ with $g^{\prime}(y_{2})=0$. Let
$N(y_{2})=\\{a_{j},x_{2},y_{21},y_{22}\\}$. If
$\\{a_{3},x_{1}\\}\sim\\{y_{21},y_{22}\\}$, then $N(x_{1})\cap V_{1}\neq
N(x_{2})\cap V_{1}$ and $a_{3}a_{4}\in E(G)$, it follows that $y_{11}y_{12}\in
E(G)$ and $\\{a_{2},y_{21},y_{22}\\}\sim\\{a_{3},x_{1},x_{3}\\}$, a
contradiction. If $\\{*,y_{11}\\}\sim\\{y_{21},y_{22}\\}$, when
$y_{11}y_{12}\in E(G)$, then $g^{\prime}(y_{11})\geq 1$ and $g^{*}(x_{1})\geq
0$; when $y_{11}y_{12}\notin E(G)$, then $d(y_{12})\geq 5$ and $y_{11}$ can
send $0.5$ charges to $x_{1}$, then $g^{*}(x_{1})\geq 0$. And
$g^{\prime}(y_{21})\geq 0.5$, $i\in[2]$, thus $g^{*}(x_{2})\geq 0$.

When there exists $x_{2}\in V^{\prime}_{2}$ and $z_{2}\in N(x_{2})\cap V_{3}$
with $g^{\prime}(z_{2})=0$, let $N(z_{2})=\\{x_{2},x_{3},z_{21},z_{22}\\}$.
Since $z_{2}y_{1}\notin E(G)$, when
$\\{y_{11},y_{12}\\}\sim\\{x_{2},x_{3}\\}$, $g^{\prime}(y_{1i})\geq 1.5$ and
$g^{*}(x_{1})\geq 0$. When $\\{y_{11},y_{12}\\}\sim\\{*,z_{21}\\}$,
$g^{\prime}(y_{1i})\geq 0.5$, $i\in[2]$ and $g^{*}(x_{1})\geq 0$. When
$\\{x_{1},y_{11}\\}\sim\\{x_{3},z_{21}\\}$, $g^{\prime}(y_{11})\geq 1$ and
$g^{*}(x_{1})\geq 0$. When $\\{x_{1},y_{11}\\}\sim\\{z_{21},z_{22}\\}$,
$g^{\prime}(y_{11})\geq 0.5$ and $g^{\prime}(z_{2i})\geq 0.5$, $i\in[2]$, thus
$g^{*}(x_{1})\geq 0$. when $\\{a_{3},x_{1}\\}\sim\\{x_{3},z_{21}\\}$,
$g^{\prime}(z_{21})\geq 1$ and $g^{*}(x_{1})\geq 0$; when
$\\{a_{3},x_{1}\\}\sim\\{z_{21},z_{22}\\}$, $x_{1}\notin\\{x_{2},x_{3}\\}$ for
otherwise there exists $z_{21}$ such that $\\{x_{2},x_{3}\\}\subseteq
N(z_{21})$, and $K_{3,3}$ occurs. Then $g^{\prime}(z_{2i})\geq 1$, $i\in[2]$
and $g^{*}(x_{1})\geq 0$.

When $\\{a_{3},y_{11}\\}\sim\\{*,*\\}$, if $y_{11}y_{12}\notin E(G)$, then
$g^{\prime}(y_{12})\geq 0.5$ and $g^{*}(x_{1})\geq 0$; if $y_{11}y_{12}\in
E(G)$ and $g^{\prime}(y_{12})=0$, then there exists another vertex $x_{4}\in
V^{\prime}_{2}$ and $z_{3}\in N(x_{4})\cap V_{4}$ with $g^{\prime}(z_{3})=0$
and $z_{3}y_{1}\notin E(G)$. If $\\{a_{3},y_{11}\\}\sim\\{x_{2},x_{3}\\}$ and
$\\{a_{3},y_{11}\\}\sim\\{x_{4},x_{5}\\}$, then there exists
$\\{x_{4},x_{5}\\}\subseteq V^{-0.5}_{2}$, $g^{*}(x_{1})\geq 0$. If
$\\{a_{3},y_{11}\\}\sim\\{x_{2},x_{3}\\}$ and
$\\{a_{3},y_{11}\\}\sim\\{*,z_{31}\\}$, $g^{\prime}(y_{11})\geq 2.5$ and
$g^{\prime}(z_{31})\geq 1$, then $g^{*}(x_{1})\geq 0$. If
$\\{a_{3},y_{11}\\}\sim\\{*,z_{21}\\}$ and
$\\{a_{3},y_{11}\\}\sim\\{*,z_{31}\\}$, then $g^{*}(x_{1})\geq 0$.

Therefore, we just consider $x\in V^{\prime}_{2}$, if $b\in N(x)\cap(V_{3}\cup
V_{4})$ with $g^{\prime}(b)=0$, then $b\in V_{4}$. When $x_{1}\in
V^{\prime}_{2}\setminus(V_{12}\cup V_{34})$, then $x_{1}\in V^{-0.5}_{2}$. If
$d(x_{1})=4$, let $N(x_{1})=\\{a_{2},a_{3},x_{11},b_{1}\\}$ where
$N(x_{11})\cap V_{1}\neq N(x_{1})\cap V_{1}$, then
$\\{a_{2},b_{1}\\}\sim\\{a_{3},x_{11}\\}$. If $d(b_{1})=4$, then there exists
$b_{11}\in N(x_{1})\cap V_{3}$, a contradiction. Thus $d(b_{1})\geq 5$ and
$g^{\prime}(b_{1})\geq 1$ and $b_{1}$ can send $0.5$ charges to $x_{1}$ and
$g^{*}(x_{1})\geq 0$. Therefore, we consider $d(x_{1})\geq 5$. If there exists
two positive neighbors of $x_{1}$, then $g^{*}(x_{1})\geq 0$. Otherwise, there
exists $z_{1}\in N(x_{1})\cap V_{4}$ with $g^{\prime}(z_{1})=0$. Let
$N(z_{1})=\\{x_{1},x_{2},z_{11},z_{12}\\}$. Since $x_{1}x_{2}\notin E(G)$,
$\\{x_{1},x_{2}\\}\sim\\{z_{11},z_{12}\\}$. When there exists $x_{3}\in
V^{\prime}_{2}$ and $z_{3}\in N(x_{3})\cap V_{4}$ with $g^{\prime}(z_{3})=0$.
Let $N(z_{3})=\\{x_{3},x_{4},z_{31},z_{32}\\}$. Since $z_{3}z_{1}\notin E(G)$,
when $\\{x_{4},z_{31}\\}\sim\\{x_{1},x_{2}\\}$, if
$\\{z_{31},z_{32}\\}\sim\\{x_{3},x_{4}\\}$, then $g^{\prime}(z_{31})\geq 1.5$,
$g^{*}(x_{i})\geq 0$, $i\in[2]$; if
$\\{z_{31},x_{3}\\}\sim\\{z_{32},x_{4}\\}$, then $g^{\prime}(z_{31})\geq 1$,
and $g^{\prime}(x_{4})\geq 0.5$, then $g^{*}(x_{i})\geq 0$, $i\in[3]$. When
$\\{x_{4},z_{31}\\}\sim\\{x_{2},z_{11}\\}$, then $g^{\prime}(z_{31})\geq 1$
and $g^{\prime}(z_{11})\geq 1$, thus $g^{*}(x_{i})\geq 0$, $i\in[2]$. When
$\\{z_{31},z_{32}\\}\sim\\{x_{2},z_{11}\\}$, then $g^{\prime}(z_{3i})\geq 1$,
$i\in[2]$, $g^{*}(x_{2})\geq 0$ and $g^{\prime}(z_{11})\geq 0.5$ thus
$g^{*}(x_{2})\geq 0$. When $\\{z_{31},z_{32}\\}\sim\\{z_{11},z_{12}\\}$, then
$g^{\prime}(z_{1i})\geq 0.5$, $i\in[2]$, thus $g^{*}(x_{i})\geq 0$, $i\in[2]$.
Therefore, we just need to consider $V^{\prime}_{12}\cup V^{\prime}_{34}$. If
$x_{1}\in V^{\prime}_{12}$ with $d(x_{1})=4$, let
$N(x_{1})=\\{a_{1},a_{2},b_{11},b_{12}\\}$, then $a_{1}a_{2}\in E(G)$ for
otherwise $\\{a_{1},a_{2}\\}\sim\\{b_{11},b_{12}\\}$, which contradict to
$x_{1}\in V^{\prime}_{2}$. Thus $\\{a_{1},b_{11}\\}\sim\\{a_{2},b_{12}\\}$ and
there exists $b_{11}a_{1}\in E(G)$. If $d(b_{12})\geq 5$, then
$g^{\prime}(b_{12})\geq 1$ and $g^{*}(x_{1})\geq 0$. Then $d(b_{12})=4$, let
$N(b_{12})=\\{a_{1},x_{1},b_{11},b_{121}\\}$ and
$\\{x_{1},b_{121}\\}\sim\\{a_{1},b_{11}\\}$. If $d(b_{121})\geq 5$,
$g^{*}(b_{121})\geq 1$ and $g^{*}(b_{11})\geq 0$ without $b_{12}$, thus
$g^{*}(x_{1})\geq 0$. If $d(b_{121})=4$, then
$N(b_{121})=\\{a_{1},b_{11},b_{12},y_{2}\\}$. Since $y_{2}b_{12}\notin E(G)$,
$\\{y_{2},b_{12}\\}\sim\\{a_{1},b_{11}\\}$. And since $b_{121}a\notin E(G)$,
either $y_{2}\in V_{2}$ or $b_{11}\in V_{12j}$ for some $j\in\\{3,4\\}$. In
both cases we have $g^{\prime}(b_{11})\geq 0$ and thus $g^{*}(x_{1})\geq 0$.

Next we consider the vertices $x_{1}\in V^{\prime}_{2}$ with $d(x_{1})\geq 5$.
When $x_{1}\in V^{\prime}_{12}$ and $z_{1}\in N(x_{1})\cap V_{4}$ with
$g^{\prime}(z_{1})=0$, let $N(z_{1})=\\{x_{1},x_{2},z_{11},z_{12}\\}$. If
$x_{1}x_{2}\notin E(G)$, then $\\{x_{1},x_{2}\\}\sim\\{z_{11},z_{12}\\}$. When
$x_{1}x_{2}\in E(G)$, $\\{x_{1},x_{2}\\}\nsim\\{z_{11},z_{12}\\}$ and
$\\{x_{1},z_{11}\\}\sim\\{x_{2},z_{12}\\}$. Since $z_{1}a_{1}\notin E(G)$,
when $\\{x_{1},x_{2}\\}\sim\\{a_{11},a_{12}\\}$ where $a_{1i}\in N(a_{1})\cap
V_{3}$, $i\in[2]$, then $g^{*}(x_{j})\geq 0$, $j\in[2]$. When
$\\{x_{2},z_{12}\\}\sim\\{x_{1},a_{11}\\}$, then $g^{\prime}(a_{11})\geq 0.5$
and $g^{\prime}(z_{12})\geq 0.5$. When
$\\{z_{11},z_{12}\\}\sim\\{x_{3},a_{11}\\}$, then $g^{\prime}(z_{1i})\geq
0.5$, $i\in[2]$. Since $z_{1}a_{2}\notin E(G)$, $g^{*}(x_{1})\geq 0$ and
$g^{*}(x_{2})\geq 0$. Therefore, we consider
$\\{x_{1},x_{2}\\}\sim\\{z_{11},z_{12}\\}$. When there exists
$x_{3}\in(V^{\prime}_{12}\cup V^{\prime}_{34})\setminus\\{x_{1},x_{2}\\}$ and
$z_{3}\in N(x_{3})\cap V_{4}$ such that $g^{\prime}(z_{3})=0$. Let
$N(z_{3})=\\{x_{3},x_{4},z_{31},z_{32}\\}$. Sicne $z_{1}z_{3}\notin E(G)$,
when $\\{x_{2},z_{11}\\}\sim\\{x_{4},z_{32}\\}$, then $x_{4}\in V_{12}$ and
since $N(z_{11})\cap V_{12}=\\{x_{1},x_{2}\\}$, $x_{4}\in\\{x_{1},x_{2}\\}$
and similarly $x_{2}\in\\{x_{3},x_{4}\\}$, thus
$\\{x_{1},x_{2}\\}=\\{x_{3},x_{4}\\}$, a contradiction. When
$\\{x_{2},z_{11}\\}\sim\\{z_{31},z_{32}\\}$, $g^{\prime}(z_{11})\geq 0.5$ and
when $x_{3}\in V_{12}$, since $\\{z_{3},z_{11},x_{2},x_{3}\\}\subseteq
N(z_{31})$ and $z_{11}x_{3},z_{3}z_{11}\notin E(G)$, $d(z_{31})\geq 5$ and
$g^{\prime}(z_{31})\geq 0.5$; when $x_{3}\in V_{34}$, $g^{\prime}(z_{3i})\geq
1$, $i\in[2]$. When $\\{z_{11},z_{12}\\}\sim\\{z_{31},z_{32}\\}$, then
$g^{\prime}(z_{1i})\geq 0.5$ and $g^{\prime}(z_{3i})\geq 0.5$, $i\in[2]$.
Since there are at least two such vertices like $x_{3}$. Thus
$g^{*}(x_{1})\geq 0$.

If $x_{1}\in V^{-1}_{2}\cap V_{12}$ and $d(x_{1})=5$, then
$g^{\prime}(z_{1})\geq 0.5$ for any $z_{1}\in N(x_{1})\cap V_{4}$. Let
$N(x_{1})=\\{a_{1},a_{2},z_{1},z_{2},z_{3}\\}$. There is $x_{2}\in
V^{\prime}_{12}$ for otherwise we can skip this case. Since $x_{1}x_{2}\notin
E(G)$, when there are at least four such vertices like $x_{1}$ in
$V^{\prime}_{12}$, there exists a vertex $z_{1}$ with $|N(z_{1})\cap
V_{4}|\geq 4$. Thus $z_{1}$ can send $0.5$ charges to $x_{1}$, and so
$g^{*}(x_{1})\geq 0$.

###  3.4 $\delta(G)=5$

Since $\delta(G)=5$, $e(G)\geq 5n/2$. Note that when $n\leq 18$, $e(G)\geq
3n-9$. So we may assume that that $n\geq 19$. We choose a vertex $a$ such that
$d(a)=5$ and $e(G[V_{1}])$ is minimum.

###### Claim 14

$\displaystyle w_{2}+w_{3}+w_{4}\geq 3.5-e(G[V_{1}\backslash\\{a\\}]).$ (9)

_Proof._ We define $V_{2}^{22}=\\{x\in V_{2}^{2}:N(x)\subseteq V_{1}\cup
V_{2}\\}$.

If $V_{3}=V_{4}=\emptyset$, then $g(x)\geq 0.5$ for any $x\in V_{2}$. Since
$n\geq 19$, $w_{2}\geq 0.5*13>3.5$ and so the claim holds. So $V_{3}\cup
V_{4}\neq\emptyset$. We first show that $w_{3}+w_{4}\geq 2$. When
$V_{4}\neq\emptyset$: for any $z\in V_{4}$, $g(z)\geq 2$ if $|V_{4}|=1$;
$g(z)\geq 1.5$ if $|V_{4}|=2$; $g(z)\geq 1$ if $|V_{4}|=3$; $g(z)\geq 0.5$ if
$|V_{4}|\geq 4$. Thus if $V_{4}\neq\emptyset$, then $w_{4}\geq 2$. When
$V_{4}=\emptyset$ and $V_{3}\neq\emptyset$: for any $y\in V_{3}$, $g(y)\geq 2$
if $|V_{3}|=1$; $g(y)\geq 1$ if $|V_{3}|\geq 2$. Thus if $V_{3}\neq\emptyset$,
then $w_{3}\geq 2$. Therefore, we can assume that that
$e(G[V_{1}\setminus\\{a\\}])\leq 1$ for otherwise the claim holds.

If $|V_{2}^{3}|\geq 2$, then $g(x)\geq 1$ for any $x\in V_{2}^{3}$, and so the
claim holds. So $|V_{2}^{3}|\leq 1$. Since $G$ is $K_{3,3}$-free,
$|V_{2}^{3}\cup V_{2}^{4}\cup V_{2}^{5}|\leq 2$. By the fact that
$e(G[V_{1}\setminus\\{a\\}])\leq 1$ and Proposition 3.1 (iii), any vertex in
$V\setminus V_{1}$ has two neighbors in $V_{2}$. So $|V_{2}|\geq 3$. This
implies that $V_{2}^{2}\neq\emptyset$.

Let $|V_{3}|=x$ and $|V_{4}|=y$. Next we calculate $w_{2}+w_{3}+w_{4}$ by two
different ways. On one hand, when $|V_{2}^{23}\cup V_{2}^{24}|$ is smaller
than $2|V_{3}\cup V_{4}|$, we have

$\displaystyle w_{2}+w_{3}+w_{4}\geq$
$\displaystyle~{}0.5|V_{2}^{22}|+|V_{2}^{3}|+0.5[5(x+y)-3x-2y]+3x+2y-3(x+y)$
$\displaystyle=$ $\displaystyle~{}0.5|V_{2}^{22}|+|V_{2}^{3}|+x+0.5y.$ (10)

On the other hand, when $|V_{2}^{23}\cup V_{2}^{24}|$ is at least $2|V_{3}\cup
V_{4}|$, we have

$\displaystyle w_{2}+w_{3}+w_{4}\geq$
$\displaystyle~{}0.5|V_{2}^{22}|+|V_{2}^{3}|+0.5\\{4x+5y-[n-6-(x+y)-|V_{2}^{22}|-|V_{2}^{3}|]\\}$
$\displaystyle+n-6-(x+y)-|V_{2}^{22}|-|V_{2}^{3}|-3(x+y)$ $\displaystyle\geq$
$\displaystyle~{}0.5|V_{2}^{3}|+2.5(x+y)+0.5[n-6-(x+y)]-3(x+y)$
$\displaystyle\geq$ $\displaystyle~{}0.5|V_{2}^{3}|+0.5(n-6)-(x+y)$
$\displaystyle\geq$ $\displaystyle~{}0.5|V_{2}^{3}|+6.5-0.5x-y.$ (11)

Recall that $V_{2}^{2}\neq\emptyset$. Without loss of generality, we may
assume that that $x\in V_{12}$. Thus $xa_{i}\notin E(G)$ for $i=3,4,5$. By
Proposition 3.1 (i), there is a $K_{2,2}$ between $N(x)$ and $N(a_{i})$ for
$i=3,4,5$. By considering where the vertices of $K_{2,2}$ come from, we can
find edges that are not computed in (3.4). By tedious case analysis, it is not
hard to see that these edges contribute 1.5 to (3.4). Therefore, we have
$w_{2}+w_{3}+w_{4}\geq\max\\{x+0.5y+1.5,6.5-0.5x-y\\}\geq 3.5.$

This completes the proof.

Acknowledgments. Shenwei Huang is partially supported by the National Natural
Science Foundation of China (11801284). Lei, Shi and Zhang are partially
supported by National Natural Science Foundation of China and Natural Science
Foundation of Tianjin (No. 17JCQNJC00300).

## References

  * [1] C.A. Barefoot, L.H. Clark, R.C. Entringer, T.D. Porter, L.A. Székely, Z. Tuza, Cycle-saturated graphs of minimum size, Discrete Math. 150(1996), 31–48.
  * [2] T. Bohman, M. Fonoberova and O. Pikhurko, The saturation function of complete partite graphs, J. Combin. 1(2010), 149–170.
  * [3] B. Bollobás, Extremal Graph Theory, Academic Press, NewYork, 1978.
  * [4] B. Bollobás, Extremal graph theory, in R. L. Graham, M. Grötschel, and L. Lovász, eds., Handbook of Combinatorics, 1231–1292. Elsevier Science B.V.,1995.
  * [5] D. Bryant and H. Fu, $C_{4}$-saturated bipartite graphs, Discrete Math. 259(1-3)(2002), 263–268.
  * [6] J.A. Bondy, Variations on the Hamiltonian theme, Can. Math. Bull. 15(1972), 57–62.
  * [7] G. Chen, R. Faudree and R. Gould, Saturation numbers of books, Electron. J. Combin. 15(2008), # 118.
  * [8] Y. Chen, Minimum $C_{5}$-saturated graphs, J. Graph Theory 61(2009), 111–126.
  * [9] Y. Chen, All minimum $C_{5}$-saturated graphs, J. Graph Theory 67(2011) 9–26.
  * [10] Y. Chen, Minimum $K_{2,3}$-saturated graphs, J. Graph Theory 76(4)(2014),309–322.
  * [11] L.H. Clark, R.P. Crane, R.C. Entringer, H.D. Shapiro, On smallest maximally nonhamiltonian graphs, Congr. Numer. 53(1986), 215–220.
  * [12] L.H. Clark, R.C. Entringer, Smallest maximally nonhamiltonian graphs, Period. Math. Hung. 15(1983), 57–68.
  * [13] L.H. Clark, R.C. Entringer, H.D. Shapiro, Smallest maximally nonhamiltonian graphs II, Graphs Comb. 8(1992), 225–231.
  * [14] P. Erdős, A. Hajnal and J. Moon, A problem in graph theory, Amer. Math. Monthly, 71(1964), 1107–1110.
  * [15] J. Faudree, R. Faudree and J. Schmitt, A survey of minimum saturated graphs, Electron. J. Combin. 18 (2011), #DS19.
  * [16] Z. Füredi, Y. Kim, Cycle-saturated graphs with minimum number of edges , J. Graph Theory, 73(2) (2013), 203–215.
  * [17] R. Gould and J. Schmitt, Minimum degree and the minimum size of $K^{t}_{2}$-saturated graphs, Discrete Math. 307(2007), 1108–1114.
  * [18] L. Kászonyi and Z. Tuza, Saturated graphs with minimal number of edges, J. Graph Theory 10(1986), 203–210.
  * [19] L. Ollmann, $K_{2,2}$-saturated graphs with a minimal number of edges, in Combinatorics, Graph Theory and Computing, Proc. 3rd Southeast. Conf., Boca Raton, (Utilitas Math., Winnipeg), (1972), 367–392.
  * [20] O. Pikhurko, The minimum size of saturated hypergraphs, Combin. Probab. Comput. 8(1999), 483–492.
  * [21] O. Pikhurko and J. Schmitt, A note on minimum $K_{2,3}$-saturated graphs, Australas J Combin. 40(2008), 211–215.
  * [22] Z. Tuza, $C_{4}$-saturated graphs of minimum size, Acta Univ. Carolin. Math. Phys. 30(1989), 161–167.
  * [23] D. West, Introduction to Graph Theory, Prentice hall, Upper Saddle River, 2001.