On total coloring of 1-planar graphs without 4-cycles

1. Introduction

All graphs considered are finite, simple and undirected. Let $G$ be a graph. We use $V(G)$, $E(G)$, $\mathrm{\Delta }(G)$ and $\delta (G)$ to denote its vertex set, edge set, maximum degree and minimum degree, respectively. For a vertex $v\in V(G)$, $N_G(v)$ denotes the set of vertices that are adjacent to $v$ in $G$. By $d(v):=|N_G(v)|$ denotes the $degree$ of $v$ in $G$. For planar graphs $G$, $F(G)$ denotes its face set, the degree of a face $f$, denoted by $d(f)$, is the length of a boundary walk around $f$ in $G$. We call $v$ a $k$-vertex, or a $k^{+}$-vertex, or a $k^{-}$-vertex if $d(v)=k$, or $d(v)\ge k$, or $d(v)\le k$ respectively and call $f$ a $k$-face, or a $k^{+}$-face, or a $k^{-}$-face if $d(f)=k$, or $d(f)\ge k$, or $d(f)\le k$ respectively. Any undefined notation follows that of Bondy and Murty [2]. A $total-k-coloring$ of a graph $G$ is a coloring of $V(G)\cup E(G)$ using $k$ colors such that no two adjacent or incident elements receive the same color. The $totalchromatic$ $number$ ${\chi }^{″}(G)$ of $G$ is the smallest integer $k$ such that $G$ has a total-$k$-coloring. It is clearly that ${\chi }^{″}(G)\ge \mathrm{\Delta }(G)+1$. Behzad and Vizing [1,6] posed independently the conjecture, ${\chi }^{″}(G)\le \mathrm{\Delta }(G)+2$ for any graph $G$, which is known as the total coloring conjecture.

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. The notion of a 1-planar graph was introduced by Ringel [4] in connection with the problem of simultaneous coloring of adjacent/incident vertices and faces of plane graphs. In [10], Zhang et al. proved that every 1-planar graph with maximum degree $\mathrm{\Delta }(G)\ge 16$ is totally $(\mathrm{\Delta }(G)+2)$-choosable, which implies that the total-coloring conjecture holds for 1-planar graphs with maximum degree at least 16. Later, Czap [3] proved (Without discharging method) that for every 1-planar graph $G$ with $\mathrm{\Delta }(G)\ge 10$ it holds ${\chi }^{″}(G)\le \mathrm{\Delta }(G)+3$. Moreover, if $\chi (G)\le 4$, then ${\chi }^{″}(G)\le \mathrm{\Delta }(G)+2$. In the same paper, the author also verified that for every 1-planar graph $G$ without adjacent triangles and with $\mathrm{\Delta }(G)\ge 10$ it holds ${\chi }^{″}(G)\le \mathrm{\Delta }(G)+3$. Moreover, if $\chi (G)\le 4$, then ${\chi }^{″}(G)\le \mathrm{\Delta }(G)+2$. Zhang and Hou [7] showed the following theorem which improve the lower bound for the maximum degree in the corollary of [10] to 13.

Recently, Sun and Wu [5] verified the total coloring ${\chi }^{″}(G)\le r+2$, for every 1-planar graph $G$ if $\mathrm{\Delta }(G)\ge 9$ and $g(G)\ge 4$ where $\mathrm{\Delta }(G)$ is the maximum degree of $G$ and $g(G)$ is the girth of $G$

In this paper, we shall prove the following results:

2. Preliminaries

Let $G$ in this paper has been embedded on a plane such that every edge is crossed by at most one other edge and the number of crossings is as small as possible. The $associated$ $plane$ $graph$ $G^{\times }$ of $G$ is obtained by turning all crossings of $G$ into new 4-vertices on a plane. For convenience, a vertex in $G^{\times }$ is called $false$ if it is not a vertex of $G$ and $real$ otherwise. A $false$ $face$ means a face $f$ in $G^{\times }$ that is incident with at least one $false$ $vertex$; otherwise, $f$ is a $normal$ $face$. For a vertex $v\in V(G^{\times })$, we use $f_k(v)$ to denote the number of $k$-faces which are incident with $v$, $n_i(v)$ to denote the number of $i$-vertices which are adjacent to $v$, and $n_c(v)$ to denote the number of false vertices which are adjacent to $v$.

For convenience, we use $v_1,v_2,\cdot \cdot \cdot ,v_d$ to denote the neighbors of a $d$-vertex $v$ in $G^{\times }$ that occur around it in a clockwise order. By $f_i$ denote the face incident with $v{v}_i$ and $v{v}_{i+1}$ in $G^{\times }$, where the addition on subscripts are taken modulo $d$.

Let $G$ be a counterexample with $|E(G)|$ as small as possible to Theorem 1.2. By minimality of $G$ we can assume that it is connected and that it has no total ($\mathrm{\Delta }(G)$ + 2)-colorings. First we investigate some structural of properties of $G$. Here, we give some known lemmas.

From this lemma, we deduce that $\delta (G)\ge 3$.

The proof is just similar to the one in [8], with only quite a little minor changes. So we omit it here and refer the reader to Lemma 4 of [8].

The proof is just similar to the one in [7], with only quite a little minor changes. So we omit it here and refer the reader to Lemma 9 of [7].

By this lemma, we deduce that each $k$-vertex ($3\le k\le 5$) has a $j$-master ($k\le j\le 5$).

3. The proof of Theorem 1.2

Then, we begin to prove the main result of the paper.

A vertex $v$ in $G$ is $small$ if $d(v)\le 5$ and is $big$ if $d(v)\ge 6$. Note that the degree of a false vertex in $G^{\times }$ is four, so every false vertex is small.

In the following, we apply the discharging method on associated 1-planar graph $G^{\times }$ of $G$ and complete the proof by a contradiction. Since $G^{\times }$ is a plane graph, we have $$\sum _{v\in V\left(G^{\times }\right)}\left(d\left(v\right)–6\right)+\sum _{f\in F\left(G^{\times }\right)}\left(2d\left(f\right)–6\right)=–12,$$ by the well-known Euler’s formular. Now we define the initial charge function $ch(x)$ of $x\in V\left(G^{\times }\right)\cup F\left(G^{\times }\right)$. Let $ch(v)=d(v)–6$ if $x\in V\left(G^{\times }\right)$ and $ch(f)=2d(f)–6$ if $x\in F\left(G^{\times }\right)$. And we define suitable discharging rules below to change the initial charge function $ch(x)$ to the final charge function $c{h}^{\prime }(x)$ on $V\left(G^{\times }\right)\cup F\left(G^{\times }\right)$. Then we still have ${\sum }_{x\in V(G^{\times })\cup F(G^{\times })}c{h}^{\prime }(x)={\sum }_{x\in V(G^{\times })\cup F(G^{\times })}ch(x)=–12$, since any discharging procedure preserves the total charge of $G^{\times }$.

Our discharging rules are defined as follows.

R1. Each $f$ in $G^{\times }$ where $d(f)\ge 4$ sends $\frac{2d(f)-6}{t(f)}$ to each small vertex incident with it, where $t(f)$ is the number of small vertices incident with the face $f$.

R2. Each 3-vertex in $G$ receives $\frac{2}{9}$ from its $i$-master ($3\le i\le 5$).

R3. Each 4-vertex in $G$ receives $\frac{6}{25}$ from its $i$-master ($4\le i\le 5$).

R4. Each $\mathrm{\Delta }$-vertex gives $\frac{1}{2}$ to a common pot from which each 3-vertex receives 1, if $|V_3|>0$.

R5. Let $w$ be a false vertex and $w$ is incident with a 3-face $f$ in $G^{\times }$, then each $8^{+}$-neighbor of $w$ on $f$ sends $\frac{13}{50}$ to $w$.

R6. Let $w$ be a real 4-vertex and $w$ is incident with a normal 3-face $f$ in $G^{\times }$, then each $8^{+}$-neighbor of $w$ on $f$ sends $\frac{13}{50}$ to $w$.

R7. Let $u$ be a real $4$ -vertex, $v$ is a false vertex in $G^{\times }$, $uv\in E(G^{\times })$ and $uv$ is incident with two 3-faces in $G^{\times }$, then $v$ sends $\frac{13}{25}$ to $u$.

R8. If a false vertex $v$ in $G^{\times }$ is incident with four $4^{+}$-faces in $G^{\times }$, then $v$ sends $\frac{5}{12}$ to each 4-neighbor of $v$.

R9. If a false vertex $v$ in $G^{\times }$ is incident with exactly one 3-face $f$ in $G^{\times }$, then $v$ sends $\frac{1}{3}$ to its 3-neighbor on $f$.

R10. Let $v$ be a 3-vertex and $v$ is not incident with any 3-face in $G^{\times }$, then $v$ sends $\frac{1}{6}$ to each false vertex which is adjacent to $v$.

R11. If a real 4-vertex $v$ in $G^{\times }$ is incident with four $4^{+}$-faces in $G^{\times }$, then $v$ sends $\frac{11}{75}$ to each false vertex which is adjacent to $v$.

R12. If a false vertex $u$ in $G^{\times }$ is adjacent to a 5-vertex $v$ in $G^{\times }$, and $uv$ is incident with $4^{+}$-faces $f_1$ and $f_2$ which are adjacent in $G^{\times }$, then $v$ sends $\frac{1}{6}$ to $u$.

In the following, we check that the final charge $c{h}^{\prime }(x)$ on each vertex and face is nonnegative, and we also show the final charge of the common pot is nonnegative. This implies that ${\sum }_{x\in V(G^{\times })\cup F(G^{\times })}c{h}^{\prime }(x)\ge 0$ for all $x\in V\left(G^{\times }\right)\cup F\left(G^{\times }\right)$, a contradiction. This completes the proof of Theorem 1.2.

First of all, by R4, the final charge of the common pot is at least $\frac{1}{2}|V_{\mathrm{\Delta }}|-|V_3|>0$ since $|V_{\mathrm{\Delta }}|>2|V_3|$ by Lemma 2.2. One can also check that the final charge of every face in $F(G^{\times })$ is nonnegative by R1. Thus in the following we consider the vertices in $G^{\times }$.

Case 1. $d=3$. By R2 and R4, $v$ receives 1 from the common pot and $\frac{2}{9}\times 3=\frac{2}{3}$ from its $i$-masters, where $3\le i\le 5$. Since $G$ is a 1-planar graph without 4-cycles, $v$ is incident with at most two 3-faces in $G^{\times }$ by Lemma 2.4 and Lemma 2.7. Now, we consider three subcases.

Case 1.1. If $v$ is not incident with any 3-face in $G^{\times }$, then $f_1,f_2,f_3$ are all $4^{+}$-faces.

First, assume that $v$ is incident with at least one $5^{+}$-face, without loss of generality, assume that $f_1$, then $v$ would receive at least 1 from $f_1$, and $\frac{2}{4}\times 2=1$ from $f_2,f_3$, by Lemma 2.5 and R1. By R10, $v$ sends at most $\frac{1}{6}\times 3=\frac{1}{2}$ to false vertices which are adjacent to $v$. Thus, $c{h}^{\prime }(v)\ge -3+1+\frac{2}{3}+1+1-\frac{1}{2}>0$.

Second, assume that $f_1,f_2,f_3$ are all 4-faces. If $v$ is adjacent to at least one real vertex in $G^{\times }$, say $v_1$, then $d(v_1)\ge 10$, thus $f_1,f_3$ sends at least $\frac{2}{3}\times 2=\frac{4}{3}$ to $v$, and $f_2$ sends at least $\frac{2}{4}=\frac{1}{2}$ to $v$ by R1. By R10, $v$ sends at most $\frac{1}{6}\times 3=\frac{1}{2}$ to false vertices which are adjacent to $v$. Thus,$c{h}^{\prime }(v)\ge -3+1+\frac{2}{3}+\frac{4}{3}+\frac{1}{2}-\frac{1}{2}=0$. Otherwise, $v_1,v_2,v_3$ are all false vertices. Let $x_i$ be the fourth(undefined) vertices of the 4-faces $f_i$ $(i=1,2,3)$. It is easy to check that $x_1{x}_2,x_2{x}_3,x_3{x}_1$$\in$$E(G)$ by the drawing of $G$. Since $f_1,f_2,f_3$ are all 4-faces, there are at least two big vertices among $x_1,x_2,x_3$ by Lemma 2.1, without loss of generality, assume that $x_1,x_2$, thus, $f_1,f_2$ send at least $\frac{2}{3}\times 2=\frac{4}{3}$ to $v$, and $f_3$ sends at least $\frac{2}{4}=\frac{1}{2}$ to $v$ by R1. By R10, $v$ sends at most $\frac{1}{6}\times 3=\frac{1}{2}$ to false vertices which are adjacent to $v$. Thus, $c{h}^{\prime }(v)\ge -3+1+\frac{2}{3}+\frac{4}{3}+\frac{1}{2}-\frac{1}{2}=0$.

Case 1.2. If $v$ is incident with exactly one 3-face in $G^{\times }$, then without loss of generality assume that $f_3$ is a 3-face. Since no two false vertices are adjacent in $G^{\times }$ by Lemma 2.4, there is a real vertex, among $v_1$ and $v_3$, say $v_1$, then $d(v_1)\ge 10$.

Assume that $v_2$ is also a real vertex, then $d(v_2)\ge 10$. Thus, $f_1$ sends at least 1 to $v$, $f_2$ sends at least $\frac{2}{4-1}=\frac{2}{3}$ to $v$ by R1, Thus,$c{h}^{\prime }(v)\ge -3+1+\frac{2}{3}+1+\frac{2}{3}>0$. Otherwise, $v_2$ is a false vertex. Let $x_i$ be the second neighbors of $v_2$ on $f_i$ $(i=1,2)$, it is easy to check that $x_1{x}_2$$\in$$E(G)$ by the drawing of $G$. Thus, at least one of $x_1$ and $x_2$ is big by Lemma 2.1. This implies that $v$ receives at least $min\{1+\frac{1}{2},\frac{2}{3}\times 2\}$$=\frac{4}{3}$, from $f_1$ and $f_2$ by R1. Therefore, $c{h}^{\prime }(v)\ge -3+1+\frac{2}{3}+\frac{4}{3}=0$.

Case 1.3. If $v$ is incident with exactly two 3-faces in $G^{\times }$, then without loss of generality assume that $f_2$ and $f_3$ are 3-faces. By Lemma 2.4 and Lemma 2.7, $v_3$ must be a real vertex, $v_1$ and $v_2$ are false vertices, and $f_1$ is a $5^{+}$-face. Thus, $f_1$ sends at least $\frac{4}{5-1}=1$ to $v$ by Lemma 2.5 and R1. Since $G$ is a 1-planar graph without 4-cycles, so, there is at least a vertex among $v_1$ and $v_2$ which is incident with exactly one 3-face, say $v_2$. Then, $v_2$ sends $\frac{1}{3}$ to $v$ by R9. Thus, $c{h}^{\prime }(v)\ge -3+1+\frac{2}{3}+1+\frac{1}{3}=0$.

Case 2. $d=4$ and $v$ is a real vertex, then $v$ has one 4-master and one 5-master. So $v$ receives totally $\frac{6}{25}\times 2=\frac{12}{25}$ from its masters by R3. Since $G$ is a 1-planar graph without 4-cycles, $v$ is incident with at most three 3-faces in $G^{\times }$ by Lemma 2.7.

If $v$ is incident with exactly one 3-face in $G^{\times }$, say $f_1$, then there is at most one false vertex among $v_1$ and $v_2$ by Lemma 2.4. Suppose that $v_1$ is a false vertex, then, $d(v_2)\ge 9$ by Lemma 2.1, thus, $v$ receives at least $\frac{2}{4-1}=\frac{2}{3}$ from $f_2$, receives $\frac{1}{2}\times 2=1$ from $f_3$ and $f_4$ by R1. Therefore, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+\frac{2}{3}+1=\frac{11}{75}$.

If $v$ is not incident with any 3-face, then $v$ is incident with four $4^{+}$-faces.

First, assume that $v$ is incident with at least one $5^{+}$-face, say $f_1$, then, $v$ receives at least 1 from $f_1$ by Lemma 2.5 and R1, receives $\frac{1}{2}\times 3=\frac{3}{2}$ from $f_2$, $f_3$ and $f_4$ by R1. $v$ sends at most $\frac{11}{75}\times 4=\frac{44}{75}$ to false vertices that are adjacent to $v$ by R11. Therefore, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+1+\frac{3}{2}-\frac{44}{75}>0$.

Second, assume that $v$ is incident with four 4-faces, if the neighbors of $v$ are all false vertices, then, let $x_i$ be the fourth(undefined) vertices of the 4-faces $f_i$ $(i=1,2,3,4)$. It is easy to check that $x_1{x}_2,x_3{x}_4$$\in$$E(G)$ by the drawing of $G$. Thus, at least one of $x_1$ and $x_2$ is big, similarly to $x_3$ and $x_4$ by Lemma 2.1. This implies that $v$ receives at least $\frac{1}{2}\times 2+\frac{2}{3}\times 2=\frac{7}{3}$ from $f_1$, $f_2$,$f_3$ and $f_4$ by R1. $v$ sends at most $\frac{11}{75}\times 4=\frac{44}{75}$ to false vertices that are adjacent to $v$ by R11. Therefore, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+\frac{7}{3}-\frac{44}{75}=\frac{17}{75}$. Otherwise, $v$ is adjacent to at least one real vertex. Thus, $v$ receives at least $\frac{1}{2}\times 4=2$ from $f_1$, $f_2$,$f_3$ and $f_4$ by R1. $v$ sends at most $\frac{11}{75}\times 3=\frac{33}{75}$ to false vertices that are adjacent to $v$ by R11. Therefore, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+2-\frac{33}{75}=\frac{3}{75}$.

If $v$ is incident with exactly three 3-faces, then without loss of generality assume that $f_1$ $f_2$ and $f_4$ are 3-faces. Since $G$ is a 1-planar graph without 4-cycles, so, $v$ is adjacent to exactly two false vertices by Lemma 2.4 and Lemma 2.7 in $G^{\times }$, and moreover $f_3$ is a $5^{+}$-face. First, assume that two false vertices are not adjacent, say $v_1$ and $v_3$, then $d(v_2)\ge 9$, $d(v_4)\ge 9$ by Lemma 2.1. Then, $f_3$ sends at least 1 to $v$ by R1, $v_1$ sends $\frac{13}{25}$ to $v$ by R7. Thus, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+1+\frac{13}{25}=0$.

Second, assume that two false vertices are $v_3$ and $v_4$, then, $d(v_1)\ge 9$, $d(v_2)\ge 9$ by Lemma 2.1. Thus, $f_3$ sends at least 1 to $v$ by R1, $v_1$ and $v_2$ send $\frac{13}{50}\times 2=\frac{13}{25}$ to $v$ by R6. This implies that $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+1+\frac{13}{25}=0$.

If $v$ is incident with exactly two 3-faces in $G^{\times }$, we consider four subcases.

Case 2.1. If $v$ is not adjacent to any false vertex, then $v_i\ge 9$ $(i=1,2,3,4)$ by Lemma 2.1, and the two 3-faces that are incident with $v$ have no common edge by Lemma 7, without loss of generality assume that $f_2$ and $f_4$ are 3-faces. Then, $v$ receives a total of $\frac{2}{4-2}\times 2=2$ from $f_1$ and $f_3$, thus, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+2>0$.

Case 2.2. If $v$ is adjacent to exactly one false vertex, without loss of generality assume that $v_1$, then $d(v_i)\ge 9$ $(i=2,3,4)$ by Lemma 2.1. First, assume that the two 3-faces that are incident with $v$ have no common edge, say $f_2$ and $f_4$, then, $v$ receives at least $\frac{2}{4-2}=1$ from $f_3$, receives at least $\frac{2}{4-1}=\frac{2}{3}$ from $f_1$ by R1, and $v$ receives $\frac{13}{50}\times 2$ from $v_2$ and $v_3$ by R6. Thus, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+1+\frac{2}{3}+\frac{13}{50}\times 2=\frac{2}{3}$. Second, assume that the two 3-faces that are incident with $v$ have one common edge, since $G$ has no 4-cycles, then, $v_1$ is incident with at least one 3-face. If $v_1$ is incident with exactly one 3-face, without loss of generality assume that $f_1$, then $f_2$ is a real 3-face in $G^{\times }$. By R6, $v$ receives $\frac{13}{50}\times 2$ from $v_2$ and $v_3$, $v$ receives at least $\frac{2}{4-2}=1$ from $f_3$ and receives at least $\frac{2}{4-1}=\frac{2}{3}$ from $f_4$ by R1. Thus, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+1+\frac{2}{3}+\frac{13}{50}\times 2=\frac{2}{3}$. If $v_1$ is incident with two 3-faces, say $f_1$ and $f_4$, then, $v$ receives at least $\frac{2}{4-2}\times 2=2$ from $f_2$ and $f_3$. Therefore, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+2=\frac{12}{25}$.

Case 2.3. If $v$ is adjacent to exactly two false vertices.

First, assume that two faces which are incident with $v$ are not adjacent, say $f_2$ and $f_4$ are both 3-faces, then, $f_1$ and $f_3$ are both $4^{+}$-faces. If two false vertices that are adjacent to $v$ are incident with the same $4^{+}$-face, say $f_1$, then, $v_1$ and $v_2$ are both false vertices, $v_3$ and $v_4$ are both big vertices. Since $G$ has no 4-cycles, then, $f_1$ is a $5^{+}$-face. It implies that $f_1$ sends at least 1 to $v$ and $f_3$ sends at least $\frac{2}{4-2}=1$ to $v$ by Lemma 2.5 and R1. Thus, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+1+1=\frac{12}{25}$. Otherwise, two false vertices that are adjacent to $v$ are incident with different $4^{+}$-faces, say $f_1$ and $f_3$, since $G$ has no 4-cycles, then, $f_1$ and $f_3$ are $5^{+}$-faces. Thus, $v$ receives at least $\frac{4}{5-1}\times 2=2$ from $f_1$ and $f_3$ by Lemma 2.5 and R1. Therefore, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+2=\frac{12}{25}$.

Second, assume that two faces which are incident with $v$ are adjacent, say $f_1$ and $f_2$ are both 3-faces, then, $f_3$ and $f_4$ are both $4^{+}$-faces. If two false vertices that are adjacent to $v$ are incident with the same $4^{+}$-face, without loss of generality assume that $v_1$ and $v_4$ are both false vertices, then, $d(v_i)\ge 9$$(i=2,3)$ by Lemma 2.1. So, $v$ receives $\frac{13}{50}\times 2=\frac{13}{25}$ from $v_2$ and $v_3$ by R6, $v$ receives at least $\frac{2}{4}\times 2=1$ from $f_3$ and $f_4$ by R1, therefore, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+\frac{13}{25}+1=0$. If two false vertices that are adjacent to $v$ are incident with different $4^{+}$-faces, say $f_3$ and $f_4$, then, $v_1$ and $v_3$ are both false vertices, and $d(v_i)\ge 9$$(i=2,4)$ by Lemma 2.1. Since $G$ has no 4-cycles, then, $f_3$ and $f_4$ are all $5^{+}$-faces. So, $v$ receives at least $\frac{4}{5-1}\times 2=2$ from $f_3$ and $f_4$ by Lemma 2.5 and R1, Therefore, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+2=\frac{12}{25}$. If two false vertices that are adjacent to $v$ are $v_2$ and $v_4$, since $G$ has no 4-cycles, there is at least one $5^{+}$-face among $f_3$ and $f_4$, say $f_3$. Thus, $f_3$ sends at least $\frac{4}{5-1}=1$ to $v$, $f_4$ sends at least $\frac{2}{4-1}=\frac{2}{3}$ to $v$ by Lemma 2.5 and R1. Therefore,$c{h}^{\prime }(v)\ge -2+\frac{12}{25}+1+\frac{2}{3}=\frac{11}{75}$.

Case 2.4. If $v$ is adjacent to exactly three false vertices, say $v_1$, $v_2$ and $v_3$, since $G$ has exactly two 3-faces, so, $f_3$ and $f_4$ are all 3-faces by Lemma 2.4, $f_1$ and $f_2$ are all $4^{+}$-faces. Since $G$ has not 4-cycles, so, $f_1$ and $f_2$ are either all 4-faces, or all $5^{+}$-faces, or there is at least one $6^{+}$-face. First assume that there is one $6^{+}$-face among $f_1$ and $f_2$, say $f_1$. Let $x_i$ $(i=1,2)$ be the second(undefined) neighbors of $v_2$ on $f_i$, it is easy to check that $x_1{x}_2$$\in$$E(G)$ by the drawing of $G$. Thus, at least one of $x_1$ and $x_2$ is big by Lemma 2.1. Then, $v$ receives at least $min\{\frac{6}{6-1}+\frac{1}{2},\frac{6}{6}+\frac{2}{4-1}\}$ $=\frac{5}{3}$ from $f_1$ and $f_2$ by R1.

Therefore, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+\frac{5}{3}=\frac{11}{75}$. Second, assume that $f_1$ and $f_2$ are all $5^{+}$-faces, then, $v$ receives at least $\frac{4}{5-1}\times 2=2$ from $f_1$ and $f_2$ by Lemma 2.5 and R1, thus, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+2=\frac{12}{25}$. Third, assume that $f_1$ and $f_2$ are all 4-faces, then, $v_2$ is incident with four 4-faces, because otherwise, $G$ has 4-cycles. By R8, $v$ receives $\frac{5}{12}$ from $v_2$. Let $x_i$ $(i=1,2)$ be the fourth(undefined) vertices of the 4-faces $f_i$, it is easy to check that $x_1{x}_2$$\in$$E(G)$ by the drawing of $G$. Thus, at least one of $x_1$ and $x_2$ is big by Lemma 2.1. This implies that $v$ receives at least $\frac{1}{2}+\frac{2}{3}=\frac{7}{6}$ from $f_1$ and $f_2$ by R1. Therefore, $c{h}^{\prime }(v)\ge -2+\frac{12}{25}+\frac{5}{12}+\frac{7}{6}=\frac{19}{300}$

Case 3. $d=4$ and $v$ is a false vertex, then, the neighbors of $v$ are real vertices, and $v$ is adjacent to at most two small vertices in $G$ by Lemma 2.1. Since $G$ has no 4-cycles, so, $v$ is incident with at most two 3-faces, we consider three subcases.

Case 3.1. If $v$ is not incident with any 3-face in $G^{\times }$, then $v$ is incident with four $4^{+}$-faces in $G^{\times }$.

Assume first that $v$ has at least one 4-neighbor, say $v_1$, then, $d(v_3)\ge 9$, moreover, there is at least one big among $v_2$ and $v_4$ by Lemma 2.1, say $v_2$, thus, $v$ would receive at least $\frac{2}{4-2}=1$ from $f_2$, at least $\frac{2}{4-1}\times 2=\frac{4}{3}$ from $f_1$ and $f_3$, at least $\frac{2}{4}=\frac{1}{2}$ from $f_4$ by R1, $v$ sends at most $\frac{5}{12}\times 2=\frac{5}{6}$ to its 4-neighbors by R8. Therefore, $c{h}^{\prime }(v)\ge -2+1+\frac{4}{3}+\frac{1}{2}-\frac{5}{6}=0$. Otherwise, $v$ does not have any 4-neighbors, then, $v$ sends out nothing by R8, $v$ would receive at least $\frac{2}{4}\times 4=2$, Thus,$c{h}^{\prime }(v)\ge -2+2=0$.

Case 3.2. If $v$ is incident with exactly one 3-face in $G^{\times }$, then without loss of generality assume that $f_1$ is the 3-face. There is at least one big among $v_1$ and $v_2$, say $v_2$.

Assume first that $v_1$ is a 3-vertex, then, both $v_2$ and $v_3$ are ${10}^{+}$-vertices by Lemma 2.1. Thus, $v$ would receive at least $\frac{2}{4-2}=1$ from $f_2$, at least $\frac{2}{4-1}=\frac{2}{3}$ from $f_3$, at least $\frac{2}{4}=\frac{1}{2}$ from $f_4$ by R1, $v$ would receive $\frac{13}{50}$ from $v_2$ by R5, $v$ sends at most $\frac{1}{3}$ to $v_1$ by R9. Thus, $c{h}^{\prime }(v)\ge -2+1+\frac{2}{3}+\frac{1}{2}+\frac{13}{50}-\frac{1}{3}=\frac{7}{75}$. Second, assume that $4\le$$d(v_1)$$\le 7$, then, both $v_2$ and $v_3$ are $6^{+}$-vertices by Lemma 2.1. So, $v$ would receive at least $\frac{2}{4-2}=1$ from $f_2$, at least $\frac{2}{4-1}=\frac{2}{3}$ from $f_3$, at least $\frac{2}{4}=\frac{1}{2}$ from $f_4$ by R1, $v$ sends out nothing by R9. Therefore,$c{h}^{\prime }(v)\ge -2+1+\frac{2}{3}+\frac{1}{2}=\frac{1}{6}$. Third, assume that $v_1$ is a $8^{+}$-vertex, then, $v_1$ sends $\frac{13}{50}$ to $v$ by R5. There is at least a big vertex among $v_2$ and $v_4$, so, $f_2$ and $f_4$ send $min\{\frac{2}{4-2}+\frac{1}{2},\frac{2}{4-1}\times 2\}$ $=\frac{4}{3}$ to $v$, $f_3$ sends $\frac{2}{4}=\frac{1}{2}$ to $v$ by R1, $v$ sends out nothing by R9. Therefore,$c{h}^{\prime }(v)\ge -2+\frac{13}{50}+\frac{4}{3}+\frac{1}{2}=\frac{7}{75}$.

Case 3.3. If $v$ is incident with two 3-faces in $G^{\times }$, since $G$ has no 4-cycles, then, the two 3-faces have a common edge, without loss of generality assume that $f_3$ and $f_4$ are 3-faces. There is a big vertex among $v_1$ and $v_3$, say $v_1$.

First assume that $6\le$$d(v_4)$$\le 7$ , then, both $v_2$ and $v_3$ are big by Lemma 2.1, moreover, $f_1$ and $f_2$ send at least $\frac{2}{4-2}\times 2=2$ to $v$ by R1, $v$ sends out nothing by R7. Thus, $c{h}^{\prime }(v)\ge -2+2=0$. Second, assume that $d(v_4)\le 5$, then, $v_i$ $(i=1,2,3)$ is $8^{+}$-vertex by Lemma 2.1, moreover, $f_1$ and $f_2$ send at least $\frac{2}{4-2}\times 2=2$ to $v$ by R1, $v_1$ and $v_3$ send $\frac{13}{50}\times 2=\frac{13}{25}$ to $v$ by R5, $v$ sends at most $\frac{13}{25}$ to $v_4$ by R7. Thus,$c{h}^{\prime }(v)\ge -2+2+\frac{13}{25}-\frac{13}{25}=0$.

Third assume that $v_4$ is a $8^{+}$-vertex. If there is at least one $5^{+}$-face among $f_1$ and $f_2$, say $f_1$, then, $f_1$ sends at least $\frac{4}{5-1}=1$ to $v$, $f_2$ sends at least $\frac{2}{4}=\frac{1}{2}$ to $v$ by Lemma 2.5 and R1, $v_4$ sends $\frac{13}{50}\times 2=\frac{13}{25}$ to $v$ by R5. Thus, $c{h}^{\prime }(v)\ge -2+1+\frac{1}{2}+\frac{13}{25}=\frac{1}{50}$. Otherwise, $f_1$ and $f_2$ are all 4-faces. Let $x_i$$(i=1,2)$ be the second(undefined) neighbors of $v_2$ on $f_i$, since $G$ has no 4-cycles, then, both $x_1$ and $x_2$ are false vertices. Suppose that $v_2$ is a $6^{+}$-vertex, then, $f_1$ sends at least $\frac{2}{4-2}=1$ to $v$, $f_2$ sends at least $\frac{2}{4-1}=\frac{2}{3}$ to $v$ by R1, $v_4$ sends $\frac{13}{50}\times 2=\frac{13}{25}$ to $v$ by R5. Thus, $c{h}^{\prime }(v)\ge -2+1+\frac{2}{3}+\frac{13}{25}=\frac{14}{75}$. Suppose that $v_2$ is a 3-vertex or a 4-vertex, since $G$ has no 4-cycles, then, $v_2$ is not incident with any 3-faces. By R10 and R11, $v_2$ sends at least $\frac{11}{75}$ to $v$. Suppose that $v_2$ is a 5-vertex, by R12,$v_2$ sends $\frac{1}{6}$ to $v$. Thus, when $v_2$ is a $5^{-}$-vertex, this implies that $v_2$ sends at least $\frac{11}{75}$ to $v$. And moreover, we consider the degree of $v_3$. If $v_3$ is a $5^{-}$-vertex, then, $v_1$ is a $8^{+}$-vertex by Lemma 2.1, $v_1$ sends $\frac{13}{50}$ to $v$, $v_4$ sends $\frac{13}{50}\times 2=\frac{13}{25}$ to $v$ by R5, $f_1$ sends at least $\frac{2}{4-1}=\frac{2}{3}$ to $v$, $f_2$ sends at least $\frac{2}{4}=\frac{1}{2}$ to $v$ by R1. Therefore, $c{h}^{\prime }(v)\ge -2+\frac{11}{75}+\frac{13}{50}+\frac{13}{25}+\frac{2}{3}+\frac{1}{2}=\frac{7}{75}$. If $v_3$ is a $6^{+}$-vertex, since $v_1$ is big, then, each of $f_1$ and $f_2$ sends at least $\frac{2}{4-1}=\frac{2}{3}$ to $v$ by R1, $v_4$ sends $\frac{13}{50}\times 2=\frac{13}{25}$ to $v$ by R5, therefore, $c{h}^{\prime }(v)\ge -2+\frac{11}{75}+\frac{2}{3}\times 2+\frac{13}{25}=0$.

Case 4. $d=5$. $v$ is incident with at most four 3-faces in $G^{\times }$ by Lemma 2.3. If $v$ would send charges to a false vertex which adjacent to $v$ by R12, then $v$ is incident with at most three 3-faces in $G^{\times }$. First assume that $v$ is incident with exactly four 3-faces in $G^{\times }$, say $f_1$, $f_2$, $f_3$ and $f_4$, then $v_1$,$v_3$, and $v_5$ are false vertices, $v_2$ and $v_4$ are real vertices by Lemma 2.8. Since $G$ has no 4-cycles, then, $f_5$ is a $6^{+}$-face. Thus, $f_5$ sends 1 to $v$ by R1, therefore, $c{h}^{\prime }(v)\ge -1+1=0$. Second assume that $v$ is incident with exactly three 3-faces in $G^{\times }$, then, $v$ is incident with two $4^{+}$-faces. If the two $4^{+}$-faces are not adjacent, then, $v$ sends out nothing by R12, $v$ would receive at least $\frac{2}{4}\times 2=1$ from two $4^{+}$-faces which are incident with $v$. Thus, $c{h}^{\prime }(v)\ge -1+1=0$. If two $4^{+}$-faces are adjacent, without loss of generality, assume that $f_1$ and $f_2$ are $4^{+}$-faces. Moreover, if $v_2$ is a real vertex, then, $v$ sends out nothing by R12, $v$ would receive at least $\frac{2}{4}\times 2=1$ from $f_1$ and $f_2$ by R1. Thus, $c{h}^{\prime }(v)\ge -1+1=0$. Otherwise, $v_2$ is a false vertex, then, $v$ sends at most $\frac{1}{6}$ to $v_2$ by R12. Let $x_i$ be the second(undefined) neighbors of $v_2$ on $f_i$ $(i=1,2)$, it is easy to check that $x_1{x}_2$$\in$$E(G)$ by the drawing of $G$. Thus, at least one of $x_1$ and $x_2$ is big by Lemma 2.1. This implies $v$ would receive at least $\frac{2}{4}+\frac{2}{4-1}=\frac{7}{6}$ from $f_1$ and $f_2$ by R1, therefore, $c{h}^{\prime }(v)\ge -1+\frac{7}{6}-\frac{1}{6}=0$. Third assume that $v$ is incident with at most two 3-faces in $G^{\times }$, then, $v$ is incident with at least three $4^{+}$-faces. $v$ sends at most $\frac{1}{6}\times 3=\frac{1}{2}$ to false vertices which are adjacent to $v$ by R12. $v$ would receive at least $\frac{2}{4}\times 3=\frac{3}{2}$ from $4^{+}$-faces which are incident with $v$, thus, $c{h}^{\prime }(v)\ge -1+\frac{3}{2}-\frac{1}{2}=0$.

Case 5. $6\le d\le 7$. Then it is trivial that $c{h}^{\prime }(v)=ch(v)\ge 0$.

Case 6. $8\le d\le \mathrm{\Delta }(G)-2$. By Lemma 2.3, $v$ is incident with at most $\lfloor \frac{4}{5}d\rfloor$ 3-faces in $G^{\times }$, then $v$ sends at most $\lfloor \frac{4}{5}d\rfloor \times \frac{13}{50}$ to false vertices and real 4-vertices which are adjacent to $v$ on 3-faces by R5 and R6. Thus, $c{h}^{\prime }(v)\ge d-6-\lfloor \frac{4}{5}d\rfloor \times \frac{13}{50}\ge \frac{99d-750}{125}>0$, since $d\ge 8$.

Case 7. $d=\mathrm{\Delta }(G)-1$. By Lemma 2.3, $v$ is incident with at most $\lfloor \frac{4}{5}d\rfloor$ 3-faces in $G^{\times }$. And by Lemma 2.1, we have $d(u)\ge 4$ if $uv\in E(G)$. So $v$ can be a 4-master vertex of at most two vertices and a 5-master vertex of at most three vertices by Lemma 2.6.

Let $\mathrm{\Delta }(G)=10$, Then, $d=9$. By Lemma 2.3, $v$ is incident with at most seven 3-faces in $G^{\times }$. If $v$ is incident with exactly seven 3-faces in $G^{\times }$, then, by Lemma 2.8, there are four consecutive 3-faces and another three consecutive 3-faces which are incident with $v$, and $v$ is adjacent to at most two real small vertices. Thus, $v$ sends at most $7\times \frac{13}{50}$ to false vertices and real 4-vertices which are adjacent to $v$ by R5 and R6. $v$ sends at most $\frac{6}{25}\times 2=\frac{12}{25}$ by R3. Therefore, $c{h}^{\prime }(v)\ge 9-6-7\times \frac{13}{50}-\frac{12}{25}=\frac{7}{10}$. If $v$ is incident with at most six 3-faces in $G^{\times }$, then, $v$ sends at most $6\times \frac{13}{50}$ to false vertices and real 4-vertices which are adjacent to $v$ by R5 and R6, $v$ sends at most $\frac{6}{25}\times 2+\frac{6}{25}\times 3=\frac{6}{5}$ to real small vertices which are adjacent to it by R3. Thus, $c{h}^{\prime }(v)\ge 9-6-6\times \frac{13}{50}-\frac{6}{5}=\frac{6}{25}$.

Let $\mathrm{\Delta }(G)\ge 11$, then, $d\ge 10$. By Lemma 2.3, $v$ is incident with at most $\lfloor \frac{4}{5}d\rfloor$ 3-faces in $G^{\times }$. $v$ sends at most $\lfloor \frac{4}{5}d\rfloor \times \frac{13}{50}$ to false vertices and real 4-vertices which are adjacent to $v$ by R5 and R6, $v$ sends out at most $\frac{6}{25}\times 2+\frac{6}{25}\times 3=\frac{6}{5}$ by R3. Thus $c{h}^{\prime }(v)\ge \mathrm{\Delta }(G)-1-6-\lfloor \frac{4}{5}(\mathrm{\Delta }(G)-1)\rfloor \times \frac{13}{50}-\frac{6}{5}\ge \frac{99\mathrm{\Delta }(G)-999}{125}\ge 0$, since $\mathrm{\Delta }(G)\ge 11$.

Case 8. $d=\mathrm{\Delta }(G)$. By Lemma 2.3, $v$ is incident with at most $\lfloor \frac{4}{5}d\rfloor$ 3-faces in $G^{\times }$. And by Lemma 2.1, we have $d(u)\ge 3$ if $uv\in E(G)$. So $v$ can be a 3-master vertex of at most one vertex, a 4-master vertex of at most two vertices and a 5-master vertex of at most three vertices by Lemma 2.6.

If $d=10$, then $v$ is incident with at most eight 3-faces. When $v$ is incident with exactly eight 3-faces, there are two groups four consecutive 3-faces that are incident with $v$ in $G^{\times }$, so, $v$ is adjacent to at most two real small vertices by Lemma 2.8. Thus, $v$ sends at most $\frac{6}{25}\times 2=\frac{12}{25}$ to real small vertices that are adjacent to it by R2 and R3, $v$ sends at most $8\times \frac{13}{50}$ to false vertices and real 4-vertices that are adjacent to $v$ by R5 and R6, and $\frac{1}{2}$ to the common pot by R4. Therefore, $c{h}^{\prime }(v)\ge 10-6-8\times \frac{13}{50}-\frac{12}{25}-\frac{1}{2}=\frac{47}{50}\ge 0$. When $v$ is incident with at most seven 3-faces, $v$ sends at most $7\times \frac{13}{50}$ to false vertices and real 4-vertices that are adjacent to $v$ by R5 and R6, $v$ sends at most $\frac{6}{25}\times 5+\frac{2}{9}=\frac{64}{45}$ to real small vertices that are adjacent to it by R2 and R3, $v$ sends $\frac{1}{2}$ to the common pot by R4. Therefore, $c{h}^{\prime }(v)\ge 10-6-7\times \frac{13}{50}-\frac{64}{45}-\frac{1}{2}=\frac{58}{225}\ge 0$.

If $d\ge 11$, $v$ sends at most $\lfloor \frac{4}{5}d\rfloor \times \frac{13}{50}$ to false vertices and real 4-vertices that are adjacent to $v$ by R5 and R6, $v$ sends at most $\frac{6}{25}\times 5+\frac{2}{9}=\frac{64}{45}$ to real small vertices adjacent to it by R2, R3 and $\frac{1}{2}$ to the common pot by R4. Thus $c{h}^{\prime }(v)\ge \mathrm{\Delta }(G)-6-\lfloor \frac{4}{5}\mathrm{\Delta }(G)\rfloor \times \frac{13}{50}-\frac{64}{45}-\frac{1}{2}\ge \frac{1782\mathrm{\Delta }(G)-17825}{2250}\ge 0$, since $\mathrm{\Delta }(G)\ge 11$.

Therefore, we complete the proof of the Theorem.