Total coloring of planar graphs without adjacent chordal 6-cycles

Abstract

A total coloring of a graph G is a coloring such that no two adjacent or incident elements receive the same color. In this field there is a famous conjecture, named Total Coloring Conjecture, saying that the the total chromatic number of each graph G is at most $\Delta +2$. Let G be a planar graph with maximum degree $\Delta \ge 7$ and without adjacent chordal 6-cycles, that is, two cycles of length 6 with chord do not share common edges. In this paper, it is proved that the total chromatic number of G is $\Delta +1$, which partly confirmed Total Coloring Conjecture.

1 Introduction

All graphs considered in this paper are simple, finite and undirected, and we follow Bondy and Murty (1976) for the terminologies and notations not defined here. A k -total-coloring of a graph G is a coloring of $V\cup {E}$ using k colors such that no two adjacent or incident elements receive the same color. A graph G is k -total-colorable if it admits a k-total-coloring. The total chromatic number $\chi ''(G)$ of G is the smallest integer k such that G is k-total-colorable. Clearly, $\chi ''(G)\ge \Delta +1$, where $\Delta$ denotes the maximum degree of G. The Total Coloring Conjecture (TCC) is a well-studied problem in graph theory, which is posed by Behzad (1965) and Vizing (1968) independently.

Conjecture 1

(TCC) For every graph G, we have $\Delta +1\le \chi ''(G)\le \Delta +2$.

TCC is confirmed for graphs with $\Delta \le 5$ (Kostochka 1996). For planar graphs, the remaining open case is just that $\Delta =6$ (Sanders and Zhao 1999). Interestingly, the total chromatic number $\chi ''(G)$ of planar graphs with large maximum degree can be determined. Until now, the best known result for planar graphs is that $\chi ''(G)=\Delta +1$ for $\Delta \ge 9$. Some other related results can be found in Cai et al. (2016), Chang et al. (2011), Hou et al. (2011), Li et al. (2015), Liu et al. (2009), Qu et al. (2016), Qu et al. (2015), Wang and Wu (2011), Wang et al. (2014), and Wang et al. (2015).

In the following, we just consider planar graphs G with $\Delta \ge 7$. Wang et al. (2014) proved that if G has no 6-cycles with chords, then $\chi ''(G)=\Delta +1$. In this paper, we obtain the following result.

Theorem 2

Suppose G is a planar graph without adjacent chordal 6-cycles. If $\Delta \ge 7$, then $\chi ''(G)=\Delta +1$.

Now we introduce some more notations and definitions here for convenience. Let G be a planar graph which is embedded on the plane. For a vertex v of G, the degree d(v) is the number of edges incident with v; and for a face f of G, the degree d(f) is the length of the boundary walk of f, where each cut-edge is counted twice. A k -vertex, $k^{-}$ -vertex or $k^{+}$ -vertex is a vertex of degree k, at most k or at leat k, respectively. Similarly, we can define a k -face, $k^{-}$ -face and $k^{+}$ -face. We say that two cycles are intersecting if they share at least one common vertex, and adjacent if they share at least one common edge. Denote by $n_{d}(v)$ the number of d-vertices adjacent to the vertex v, by $n_{d}(f)$ the number of d-vertices incident with the face f, and by $f_{d}(v)$ the number of d-faces incident with the vertex v.

2 Proof of Theorem 2

In Wang et al. (2016), Theorem 2 was proved for $\Delta \ge 8$. So we assume $\Delta =7$ in the following. Let $G=(V,E,F)$ be a minimal counterexample to Theorem 2 in terms of the number of vertices and edges. That is, every proper subgraph of G is 8-total-colorable, but not G. So G is 2-connected, and the boundary of each face in G is exactly a cycle, i.e., the boundary walk of each face cannot pass though a vertex v more than once. We first show some known properties of G.

(i) If $uv \in E(G)$ with $d(u)\le 4$, then $d(v)\ge 9-d(u)$ (see Borodin 1989; Wang and Wu 2004).

(ii) The subgraph $G_{27}$ of G induced by all edges joining 2-vertices to 7-vertices is a forest (see Borodin 1989).

(iii) If v is a 7-vertex of G with $n_2(v)\ge 1$, then $n_{4^+}(v)\ge 1$ (see Chang et al. 2011).

(iv) G has no configurations depicted in Fig. 1 where the vertices marked by $\bullet$ have no other neighbors in G (see Borodin et al. 1997; Liu et al. 2009; Shen and Wang 2009; Wang 2007).

Fig. 1

Reducible configurations

Lemma 1

(Kostochka 1996) Suppose that v is a 7-vertex and that $v_{1}, v_{2}, \cdots , v_{k}$ are consecutive neighbors of v with $d(v_{1})=d(v_{k})=2$ and $d(v_{i})\ge 3$ for $2\le i\le k-1$, where $k\in \{3, 4, 5, 6\}$. If the face incident with $v, v_{i}, v_{i+1}$ is a 4-face for all $1\le i\le k-1$, then at least one vertex in $\{v_{2}, v_{3}, \cdots , v_{k-1}\}$ is a $4^{+}$-vertex.

Lemma 2

(Wang and Wu 2011) Let $u, v_{1}, v_{2}, \cdots , v_{k}$ be neighbors of v with $d(u)=d(v_{1})=2, d(v_{k})\ge 5$, $v_{1}, v_{2}, \cdots , v_{k}$ are consecutive neighbors of v, and $d(v_{i})\ge 3$ for $2\le i\le k$, where $k\in \{3, 4, 5, 6\}$. If the face incident with $v, v_{i}, v_{i+1}$ is a 4-face $vv_{i}x_{i}v_{i+1}$ for any $1\le i\le k-2$, and the face incident with $v,v_{k-1},v_{k}$ is a 3-face, then at least one vertex in $\{v_{1}, v_{2}, \cdots , v_{k-1}\}$ is a $4^{+}$-vertex.

By the Euler’s formula $|V|-|E|+|F|=2$, we have

$$\begin{aligned} \sum _{v\in V}(2d(v)-6)+\sum _{f\in F}(d(f)-6)=-12<0. \end{aligned}$$

We define the initial charge c(x) of $x\in V\cup F$ to be $c(v)=2d(v)-6$ if $v\in V$ and $c(f)=d(v)-6$ if $f\in F$. It follows that $\sum _{x\in V\cup F}c(x)=-12<0$. Now we design appropriate rules and redistribute weights accordingly. Note that any discharging procedure preserves the total charge of G. If we can define suitable discharging rules to charge the initial charge function c to the final function $c'$ on $x\in V\cup F$, such that $c'(x)\ge 0$ for all $x\in V\cup F$, then we get an obvious contradiction.

In the following we use $c(x\rightarrow y)$ to denote the total charge from an element x to another element y. Our discharging rules are defined as follows.

R1 :

. Let v be a 2-vertex, then v receives charge 1 from each of its adjacent vertices.

R2 :

. Let v be a 4-vertex and f be a k-face incident with v. Then

(1):

$c(v\rightarrow f)=\frac{1}{5}$, if $k=5$;

(2):

$c(v\rightarrow f)=\frac{1}{2}$, if $k=4$;

(3):

$c(v\rightarrow f)=\frac{1}{2}$, if $k=3$ and $f_{3}(v)=4$;

(4):

$c(v\rightarrow f)=\frac{2}{3}$, if $k=3$ and $f_{3}(v)=3$;

(5):

$c(v\rightarrow f)=\frac{3}{4}$, if $k=3$, $f_{3}(v)=2$ and $f_{6^+}(v)\le 1$;

(6):

$c(v\rightarrow f)=1$, if $k=3$, $f_{3}(v)=2$ and $f_{6^+}(v)=2$;

(7):

$c(v\rightarrow f)=\frac{3}{4}$, if $k=3$, $f_{3}(v)=1$, $f_{4}(v)=2$ and $f_5(v)=1$;

(8):

$c(v\rightarrow f)=1$, if $k=3$, $f_{3}(v)=1$, $f_{4}(v)=2$ and $f_5(v)=0$;

(9):

$c(v\rightarrow f)=1$, if $k=3$, $f_{3}(v)=1$, $f_{4}(v)\le 1$.

R3 :

. Let v be a 5-vertex and f be a k-face incident with v. If f is incident with a 4-vertex, then let this 4-vertex be u. Then

(1):

$c(v\rightarrow f)=\frac{1}{5}$, if $k=5$;

(2):

$c(v\rightarrow f)=\frac{1}{2}$, if $k=4$;

(3):

$c(v\rightarrow f)=1$, if $k=3$ and $f_{3}(v)=4$;

(4):

$c(v\rightarrow f)=1$, if $k=3$ and $n_{4}(f)=0$;

(5):

$c(v\rightarrow f)=\frac{5}{4}$, if $k=3$, $n_{4}(f)=1$ and $f_3(u)\ge 3$;

(6):

$c(v\rightarrow f)=\frac{5}{4}$, if $k=3$, $n_{4}(f)=1$, $f_3(u)=2$ and $f_{6^+}(u)\le 1$;

(7):

$c(v\rightarrow f)=1$, if $k=3$, $n_{4}(f)=1$, $f_3(u)=2$ and $f_{6^+}(u)=2$;

(8):

$c(v\rightarrow f)=\frac{5}{4}$, if $k=3$, $n_{4}(f)=1$ and $f_3(u)=1$, $f_4(u)=2$, $f_5(u)=1$;

(9):

$c(v\rightarrow f)=1$, if $k=3$, $n_{4}(f)=1$ and $f_3(u)=1$, $f_4(u)=2$, $f_5(u)=0$;

(10):

$c(v\rightarrow f)=1$, if $k=3$, $n_{4}(f)=1$ and $f_3(u)=1$, $f_4(u)\le 1$.

R4 :

. Let v be a 6-vertex or 7-vertex and f be a k-face incident with v. If f is incident with a 4-vertex, then let this 4-vertex be u. Then

(1):

$c(v\rightarrow f)=\frac{1}{8}$, if $d(v)=7$, $k=6$ and it appears in Fig. 2(1);

(2):

$c(v\rightarrow f)=\frac{7}{16}$, if $k=5$ and it appears in Fig. 2(2);

(3):

$c(v\rightarrow f)=\frac{1}{8}$, if $k=5$ and it appears in Fig. 2(2);

(4):

$c(v\rightarrow f)=\frac{1}{3}$, if $k=5$ and it not appears in Fig. 2(2);

(5):

$c(v\rightarrow f)=1$, if $k=4$ and $n_{3^-}(f)=2$;

(6):

$c(v\rightarrow f)=\frac{3}{4}$, if $k=4$, $n_{3^-}(f)=1$ and $n_{5^-}(f)=2$;

(7):

$c(v\rightarrow f)=\frac{2}{3}$, if $k=4$, $n_{3^-}(f)=1$ and $n_{5^-}(f)\le 1$;

(8):

$c(v\rightarrow f)=\frac{1}{2}$, if $k=4$ and $n_{3^-}(f)=0$;

(9):

$c(v\rightarrow f)=\frac{3}{2}$, if $k=3$ and $n_{3^-}(f)=1$;

(10):

$c(v\rightarrow f)=\frac{5}{4}$, if $k=3$, $n_{4}(f)=1$ and $f_3(u)\ge 3$;

(11):

$c(v\rightarrow f)=\frac{5}{4}$, if $k=3$, $n_{4}(f)=1$, $f_3(u)=2$ and $f_{6^+}(u)\le 1$;

(12):

$c(v\rightarrow f)=1$, if $k=3$, $n_{4}(f)=1$, $f_3(u)=2$ and $f_{6^+}(u)=2$;

(13):

$c(v\rightarrow f)=\frac{5}{4}$, if $k=3$, $n_{4}(f)=1$ and $f_3(u)=1$, $f_4(u)=2$, $f_5(u)=1$;

(14):

$c(v\rightarrow f)=1$, if $k=3$, $n_{4}(f)=1$ and $f_3(u)=1$, $f_4(u)=2$, $f_5(u)=0$;

(15):

$c(v\rightarrow f)=1$, if $k=3$, $n_{4}(f)=1$ and $f_3(u)=1$, $f_4(u)\le 1$;

(16):

$c(v\rightarrow f)=1$, if $k=3$ and $n_{4^-}(f)=0$.

R5 :

. Let f be a 6-face and v be a 7-vertex incident with f. If it appears in Fig. 2(1), then $c(f\rightarrow v)=\frac{1}{4}$.

R6 :

. Let f be a $7^{+}$-face and v be a 7-vertex incident with f. If it appears in Fig. 2(3), then $c(f\rightarrow v)=\frac{1}{2}$.

Fig. 2

Some discharging rules

In the following, we will check that $c'(x)\ge 0$ holds for all $x\in V\cup F$ which will be the desired contradiction.

Let $v_{i}$ be the neighbor of v and $f_{i}$ be the face incident with v for $i=1,2,\cdots ,d(v)$ in anticlockwise order, where $v_{i}$ is incident with $f_{i-1}$ and $f_{i}$ ($i=1,2,\cdots ,d(v)$). Note that eventually $f_{0}$ and $f_{d(v)}$ denote the same face.

First, we consider the final charge of faces. Let f be a face of G. Suppose $d(f)\ge 7$. Then $n_{2}(f)\le \lfloor \frac{d(f)-1}{2}\rfloor$. So $c'(f)\ge c(f)-\frac{1}{2}\times (\lfloor \frac{d(f)-1}{2}\rfloor -1)\ge 0$ by R6. Suppose $d(f)=6$. Then $c(f)=0$ and $c'(f)\ge 0-\frac{1}{4}+\frac{1}{8}\times 2=0$ by R4-1 and R5. Suppose $d(f)=5$. Then $c(f)=-1$ and $n_{3^-}(f)\le 2$. If $n_{3^-}(f)=2$, then $c'(f)\ge -1+\frac{1}{8}+\frac{7}{16}\times 2=0$ by R4-2,3. If $n_{3^-}(f)=1$, then $c'(f)\ge -1+\frac{1}{3}\times 2+\frac{1}{5}\times 2=\frac{1}{15}>0$ by R2-1, R3-1 and R4-4. If $n_{3^-}(f)=0$, then $c'(f)\ge -1+\frac{1}{5}\times 5=0$ by R2-1 and R3-1. Suppose $d(f)=4$. Then $c(f)=-2$ and $n_{3^-}(f)\le 2$. If $n_{3^-}(f)=2$, then $c'(f)\ge -2+1\times 2=0$ by R4-5. If $n_{3^-}(f)=1$ and $n_{5^-}(f)=2$, then $c'(f)\ge -2+\frac{3}{4}\times 2+\frac{1}{2}=0$ by R2-2, R3-2 and R4-6. If $n_{3^-}(f)=1$ and $n_{5^-}(f)\le 1$, then $c'(f)\ge -2+\frac{2}{3}\times 3=0$ by R4-7. If $n_{3^-}(f)=0$, then $c'(f)\ge -2+\frac{1}{2}\times 4=0$ by R2-2, R3-2 and R4-8. Suppose $d(f)=3$. Then $c(f)=-3$ and $n_{3^-}(f)\le 1$. If $n_{3^-}(f)=1$, then $c'(f)\ge -3+\frac{3}{2}\times 2=0$ by R4-9. If $n_{3^-}(f)=0$ and $n_{4^-}(f)=1$, then $c'(f)\ge -3+\min \{\frac{5}{4}\times 2+\frac{3}{4}, \frac{5}{4}\times 2+\frac{2}{3}, \frac{5}{4}\times 2+\frac{1}{2}, 1\times 3\}=0$. If $n_{3^-}(f)=0$ and $n_{4^-}(f)=0$, then $c'(f)\ge -3+1\times 3=0$ by R3-4 and R4-16.

Second, we consider the final charge of vertices. There are two useful lemmas as follows.

Lemma 3

(Wang and Wu 2011) Suppose that $d(v_{1})=d(v_{k})=2$, and $d(v_{j})\ge 3$ for $j=2,3, \cdots , k-1$. If $f_{1}, f_{2}, \cdots , f_{k-1}$ are $4^{+}$-faces, then v sends in total at most $\frac{3}{2}+(k-3)$ to $f_{1}, f_{2}, \cdots , f_{k-1}$.

Lemma 4

(Wang et al. 2016) Suppose that $d(v_{1})=d(v_{k})=2$, and $d(v_{j})\ge 3$ for $j=2,3, \cdots , k-1$. If $\min \{d(f_{2}), d(f_{3}), \cdots , d(f_{k-2})\}\ge 3$, then v sends in total at most $\frac{3}{2}+\frac{5}{4}\times (k-3)$ to $f_{1}, f_{2}, \cdots , f_{k-1}$.

Let $v\in V$. Note that G has no vertex of degree one by (i). If $d(v)=2$, then $c(v)=-2$ and $c'(v)= -2+1\times 2=0$ by R1. If $d(v)=3$, then clearly $c'(v)= c(v)=0$. In the following, it suffices to check that $c'(v)\ge 0$ for all $4^{+}$-vertices of G.

Let v be a 4-vertex. We have $c(v)=2$, $n_{4^-}(v)=0$ and $f_3(v)\le 4$. If $f_3(v)=4$, then $c'(v)=2-\frac{1}{2}\times 4=0$ by R2-3. If $f_3(v)=3$, then $f_{6^{+}}(v)\ge 1$. So $c'(v)=2-\frac{2}{3}\times 3=0$ by R2-4. If $f_3(v)=2$, then $f_4(v)\le 1$ and the two $4^{+}$-faces incident with v can not be both 5-faces. If one of the $4^{+}$-faces is a 4-face, then the other $4^{+}$-face must be a $6^{+}$-face. So $c'(v)\ge 2-\max \{\frac{3}{4}\times 2+\frac{1}{2},\frac{3}{4}\times 2+\frac{1}{5}, 1\times 2\}=0$ by R2-5,6. If $f_3(v)=1$, then $f_4(v)\le 2$. If $f_4(v)=2$, then $c'(v)\ge 2-\max \{\frac{3}{4}+\frac{1}{2}\times 2+\frac{1}{5}, 1+\frac{1}{2}\times 2\}=0$ by R2-7,8. If $f_4(v)\le 1$, then $c'(v)\ge 2-1-\frac{1}{2}-\frac{1}{5}\times 2=\frac{1}{10}>0$ by R2-9. If $f_3(v)=0$, then $c'(v)\ge 2-\frac{1}{2}\times 4=0$.

Let v be a 5-vertex. We have $c(v)=4$, $n_{3^-}(v)=0$ and $f_3(v)\le 4$. If $f_3(v)=4$, then $f_{6^{+}}(v)\ge 1$. So $c'(v)=4-1\times 4=0$ by R3-3. Suppose $f_3(v)=3$. If all the 3-faces incident with v are $(4,5^{+},5)$-faces, then $f_{6^+}(v)\ge 2$ by Wang et al. (2014). So $c'(v)\ge 4-\frac{5}{4}\times 3=\frac{1}{4}>0$. Otherwise, one of the 3-faces incident with v is a $(5^{+},5^{+},5)$-face, then $f_4(v)\le 1$. If one of the $4^{+}$-faces is a 4-face, then the other $4^{+}$-face must be a $6^{+}$-face. So $c'(v)\ge 4-\frac{5}{4}\times 2-1-\max \{\frac{1}{2}, \frac{1}{5}\times 2\}=0$. If $f_3(v)\le 2$, then $c'(v)\ge 4-\frac{5}{4}\times f_3(v)-\frac{1}{2}\times [5-f_3(v)]\ge 0$.

Let v be a 6-vertex. We have $c(v)=6$, $n_{2}(v)=0$ and $f_3(v)\le 4$. If $f_3(v)=4$, then $f_{6^{+}}(v)\ge 2$. So $c'(v)=6-\frac{3}{2}\times 4=0$. If $f_3(v)=3$, then $f_4(v)\le 1$. So $c'(v)\ge 6-\max \{\frac{3}{2}\times 2+\frac{5}{4}+\frac{2}{3},\frac{3}{2}+\frac{5}{4}\times 2+\frac{3}{4}, \frac{5}{4}\times 3+1\}-\frac{7}{16}\times 2=\frac{5}{24}>0$. If $f_3(v)=2$, then $f_4(v)\le 3$. If $f_4(v)=3$, then $c'(v)\ge 6-\max \{\frac{3}{2}+\frac{5}{4}+\frac{3}{4}+\frac{2}{3}\times 2, \frac{5}{4}\times 2+\frac{3}{4}\times 3\}-\frac{7}{16}=\frac{35}{48}>0$. If $f_4(v)\le 2$, then $c'(v)=6-\frac{3}{2}\times 2-1\times 2-\frac{7}{16}\times 2=\frac{1}{8}>0$. If $f_3(v)=1$, then $f_4(v)\le 3$. So $c'(v)\ge 6-\frac{3}{2}-1\times 3-\frac{7}{16}\times 2=\frac{5}{8}>0$. If $f_3(v)=0$, then $c'(v)\ge 6-1\times 6=0$.

Let v be a 7-vertex. We have $c(v)=8$, $n_{2}(v)\le 6$ and $f_3(v)\le 4$. So it suffices to consider the following cases.

Case 1 $n_{2}(v)=6$. Then $n_{3}(v)=0$, $f_3(v)=0$ and $f_{6^{+}}(v)\ge 5$ by (iv). So $c'(v)\ge 8-1\times 6-\frac{3}{2}=\frac{1}{2}>0$ by R1 and Lemma 4.

Case 2 $n_{2}(v)=5$. Then $n_{3}(v)\le 1$ and there are three possibilities in which 2-vertices are located. They are shown as configurations in Fig. 3, where the vertices marked by $\bullet$ are 2-vertices. For Fig. 3(1), we have $f_{3}(v)\le 1$ and $f_{6^{+}}(v)\ge 4$. So $c'(v)\ge 8-1\times 5-(\frac{3}{2}+\frac{5}{4})=\frac{1}{4}>0$ by Lemma 4. For Fig. 3(2) and 3(3), we have $f_{3}(v)=0$ and $f_{6^{+}}(v)\ge 3$. So $c'(v)\ge 8-1\times 5-\frac{3}{2}\times 2=0$ by Lemma 4.

Fig. 3

The cases of 7-vertices

Case 3 $n_{2}(v)=4$. Then $n_{3}(v)\le 2$. For Fig. 3(4), $c'(v)\ge 8-1\times 4-(\frac{3}{2}+\frac{5}{4}\times 2)=0$. For Fig. 3(5) and (6), we have $f_3(v)\le 1$ and $f_{6^{+}}(v)\ge 2$. So $c'(v)\ge 8-1\times 4-\frac{3}{2}-(\frac{3}{2}+\frac{5}{4})+\frac{1}{4}\times 2=\frac{1}{4}>0$ by R5. For Fig. 3(7), we have $f_3(v)=0$, $f_4(v)\le 4$ and $f_{6^{+}}(v)\ge 1$. If $f_4(v)=4$, then $c'(v)\ge 8-1\times 4-\max \{\frac{3}{2}\times 2+\frac{7}{16}\times 2, \frac{3}{2}+1\times 2+\frac{1}{8}\times 2\}=\frac{1}{8}>0$. If $f_4(v)\le 3$, then $c'(v)\ge 8-1\times 4-\max \{\frac{3}{2}+1+\frac{1}{8}+\frac{7}{16}\times 2, 1\times 3+\frac{1}{8}\times 3\}=\frac{1}{2}>0$.

Case 4 $n_{2}(v)=3$. For Fig. 3(8), we have $f_3(v)\le 3$ and $f_{6^{+}}(v)\ge 2$. So $c'(v)\ge 8-1\times 3-(\frac{3}{2}+\frac{5}{4}\times 3)+\frac{1}{4}\times 2=\frac{1}{4}>0$ by R5. For Fig. 3(9), we have $f_3(v)\le 2$ and $f_{6^{+}}(v)\ge 1$. If $f_3(v)=0$, then $c'(v)\ge 8-1\times 3-(\frac{3}{2}+2)-\frac{3}{2}=0$ by Lemma 3. If $f_3(v)=1$, then $f_4(v)\le 4$. If the 3-face is a $(3,6^{+},7)$-face, then $c'(v)\ge 8-1\times 3-\max \{\frac{3}{2}\times 2+1+\frac{2}{3}+\frac{1}{8}, \frac{3}{2}+1+\frac{3}{4}\times 2+\frac{2}{3}+\frac{1}{8}\}=\frac{5}{24}>0$ by (iv). Otherwise, $c'(v)\ge 8-1\times 3-\frac{5}{4}-1\times 2-\frac{3}{4}\times 2-\frac{1}{8}=\frac{1}{8}>0$. If $f_3(v)=2$, then $f_{2}$ and $f_{5}$ can not be both 4-faces. So $c'(v)\ge 8-1\times 3-\max \{\frac{3}{2}\times 3+\frac{1}{8}\times 2, \frac{3}{2}\times 2+\frac{5}{4}+\frac{3}{4}+\frac{1}{8}\}+\frac{1}{4}=\frac{1}{8}>0$ by R5. For Fig. 3(10), we have $f_3(v)\le 2$ and $f_{6^{+}}(v)\ge 1$. If $f_3(v)=0$, then $c'(v)\ge 8-1\times 3-(\frac{3}{2}+1)\times 2=0$. If $f_3(v)=1$, then $c'(v)\ge 8-1\times 3-(\frac{3}{2}+1)-\max \{\frac{3}{2}+\frac{2}{3}+\frac{1}{8}, \frac{5}{4}+\frac{3}{4}\times 2\}+\frac{1}{4}=0$ by Lemma 2. If $f_3(v)=2$, then $f_4(v)\le 4$. If $f_4(v)=4$, then $f_{1}$ is a $7^{+}$-face. So $c'(v)\ge 8-1\times 3-(\frac{5}{4}+\frac{3}{4}\times 2)\times 2+\frac{1}{2}=0$ by R6. If $f_4(v)\le 3$, then $c'(v)\ge 8-1\times 3-\frac{5}{4}-\frac{3}{4}\times 2-\max \{\frac{3}{2}+\frac{2}{3}+\frac{1}{8}, \frac{5}{4}+\frac{3}{4}+\frac{7}{16}\}+\frac{1}{4}=\frac{1}{16}>0$. For Fig. 3(11), we have $f_3(v)\le 1$ and $f_4(v)\le 4$. If $f_3(v)=0$, then $c'(v)\ge 8-1\times 3-\max \{1\times 4+\frac{1}{8}\times 3, \frac{3}{2}+1\times 2+\frac{7}{16}+\frac{1}{8}\times 2\}=\frac{5}{8}>0$. If $f_3(v)=1$, then $c'(v)\ge 8-1\times 3-\max \{\frac{5}{4}+\frac{3}{4}\times 2+2\times \max \{1+\frac{1}{8}, \frac{3}{4}+\frac{1}{3}, \frac{2}{3}+\frac{7}{16}\}, \frac{3}{2}\times 2+1+\frac{2}{3}+\frac{1}{8}, \frac{3}{2}+\frac{5}{4}+1+\frac{3}{4}+\frac{1}{8}\}=0$.

Case 5 $n_{2}(v)=2$. For Fig. 3(12), we have $f_3(v)\le 4$ and $f_{5^{+}}(v)\ge 1$. If $f_3(v)=0$, then $c'(v)\ge 8-1\times 2-(\frac{3}{2}+4)=\frac{1}{2}>0$. If $f_3(v)=1$, then $f_4(v)\le 4$. So $c'(v)\ge 8-1\times 2-\frac{3}{2}-1\times 3-\frac{1}{8}-\max \{1+\frac{1}{8}, \frac{3}{4}+\frac{1}{3}, \frac{2}{3}+\frac{7}{16}\}=\frac{1}{4}>0$. Suppose $f_3(v)=2$. If $f_{3}$ and $f_{4}$ or $f_{4}$ and $f_{5}$ are 3-faces, then $f_4(v)\le 2$. So $c'(v)\ge 8-1\times 2-\frac{3}{2}\times 2-1\times 2-\frac{7}{16}\times 2-\frac{1}{8}=0$. Otherwise, $f_4(v)\le 4$. If $f_4(v)\le 2$, then $c'(v)\ge 8-1\times 2-\frac{3}{2}\times 2-1\times 2-\frac{7}{16}\times 2-\frac{1}{8}=0$. Otherwise, $c'(v)\ge 8-1\times 2-\max \{\frac{3}{2}\times 2+\frac{1}{8}+\max \{1+\frac{2}{3}\times 2+\frac{1}{8}, \frac{3}{4}\times 2+\frac{2}{3}+\frac{7}{16}\}, \frac{3}{2}+\frac{5}{4}+\frac{1}{8}+\max \{1+\frac{3}{4}\times 2+\frac{1}{8}, 1+\frac{3}{4}+\frac{2}{3}+\frac{7}{16}, \frac{3}{4}\times 3+\frac{1}{3}\}, \frac{5}{4}\times 2+1+\frac{3}{4}\times 2+\frac{7}{16}+\frac{1}{8}\}=\frac{13}{48}>0$. If $f_3(v)=3$, then $f_4(v)\le 2$. So $c'(v)\ge 8-1\times 2-\max \{\frac{3}{2}\times 3+\frac{2}{3}+\frac{1}{8}\times 3, \frac{3}{2}\times 2+\frac{5}{4}+\max \{1+\frac{1}{8}\times 3, \frac{3}{4}+\frac{2}{3}+\frac{1}{8}\times 2\}, \frac{3}{2}+\frac{5}{4}\times 2+1+\frac{3}{4}+\frac{1}{8}\times 2, \frac{5}{4}\times 3+1\times 2+\frac{1}{8}\times 2\}=0$. If $f_3(v)=4$, then $f_{6^{+}}(v)\ge 2$. So $c'(v)\ge 8-1\times 2-\frac{3}{2}\times 2-\frac{5}{4}\times 2-\frac{1}{8}\times 3=\frac{1}{8}>0$. For Fig. 3(13), we have $f_3(v)\le 3$. If $f_3(v)=0$, then $c'(v)\ge 8-1\times 2-\frac{3}{2}-(\frac{3}{2}+3)=0$. If $f_3(v)=1$, then $c'(v)\ge 8-1\times 2-\frac{3}{2}\times 2-1\times 2-\frac{2}{3}-\frac{1}{8}=\frac{5}{24}>0$. Suppose $f_3(v)=2$. If $f_{3}$ and $f_{4}$ are 3-faces, then $c'(v)\ge 8-1\times 2-\frac{3}{2}\times 3-\frac{1}{8}-\max \{1+\frac{1}{8}, \frac{3}{4}+\frac{1}{3}, \frac{2}{3}+\frac{7}{16}\}=\frac{1}{4}>0$. Otherwise, $c'(v)\ge 8-1\times 2-\max \{\frac{3}{2}\times 3+\frac{2}{3}+\frac{7}{16}+\frac{1}{8}, \frac{5}{4}\times 2+\frac{3}{4}\times 2+\max \{1+\frac{3}{4}+\frac{1}{8}, \frac{2}{3}+\frac{7}{16}\times 2\}\}=\frac{1}{8}>0$. If $f_3(v)=3$, then $f_4(v)\le 2$. So $c'(v)\ge 8-1\times 2-\max \{\frac{3}{2}\times 3+1+\frac{1}{8}\times 2, \frac{3}{2}+\frac{5}{4}\times 2+1+\frac{3}{4}+\frac{1}{8}\times 2\}=0$. For Fig. 3(14), we have $f_3(v)\le 3$. If $f_3(v)=0$, then $c'(v)\ge 8-1\times 2-(\frac{3}{2}+1)-(\frac{3}{2}+2)=0$. If $f_3(v)=1$, then $f_4(v)\le 4$. If $f_4(v)=4$, then $c'(v)\ge 8-1\times 2-\max \{\frac{3}{2}+1\times 3+\frac{2}{3}+\frac{1}{8}\times 2, \frac{5}{4}+1\times 2+\frac{3}{4}\times 2+\frac{7}{16}\times 2\}=\frac{3}{8}>0$. If $f_4(v)\le 3$, then $c'(v)\ge 8-1\times 2-\frac{3}{2}-1\times 3-\frac{7}{16}\times 3=\frac{3}{16}>0$. Suppose $f_3(v)=2$. If $f_{3}$ and $f_{4}$ are 3-faces, then $f_4(v)\le 2$. If $f_4(v)=2$, then $c'(v)\ge 8-1\times 2-\max \{\frac{3}{2}\times 2+1+\frac{1}{8}\times 2+\max \{1+\frac{1}{8}, \frac{3}{4}+\frac{1}{3}, \frac{2}{3}+\frac{7}{16}\}, \frac{3}{2}+\frac{5}{4}+\max \{1\times 2+\frac{7}{16}+\frac{1}{8}\times 2, 1+\frac{3}{4}+\frac{7}{16}\times 3\}, \frac{5}{4}\times 2+1\times 2+\frac{7}{16}\times 2+\frac{1}{8}\}=\frac{3}{16}>0$. If $f_4(v)\le 1$, then $c'(v)\ge 8-1\times 2-\max \{\frac{3}{2}\times 2+1+\frac{1}{8}\times 2+\frac{7}{16}\times 2, \frac{3}{2}+\frac{5}{4}+1+\frac{7}{16}\times 4\}=\frac{1}{2}>0$. If $f_{3}$ and $f_{7}$ are 3-faces, then $c'(v)\ge 8-1\times 2-\max \{\frac{3}{2}\times 2+\frac{1}{8}\times 2+\max \{1+\frac{2}{3}\times 2, 1+\frac{2}{3}+\frac{7}{16}\}, \frac{3}{2}+\frac{5}{4}+\frac{7}{16}+\frac{1}{8}+\max \{1+\frac{3}{4}\times 2, 1+\frac{3}{4}+\frac{2}{3}\}, \frac{5}{4}\times 2+1+\frac{3}{4}\times 2+\frac{7}{16}\times 2\}=\frac{1}{8}>0$. If $f_3(v)=3$, then $f_4(v)\le 2$. If $f_4(v)=2$, then $c'(v)\ge 8-1\times 2-\frac{3}{2}\times 2-\frac{5}{4}-\frac{3}{4}\times 2-\frac{1}{8}\times 2=0$. If $f_4(v)\le 1$, then $c'(v)\ge 8-1\times 2-\max \{\frac{3}{2}\times 3+\frac{2}{3}+\frac{1}{8}\times 3, \frac{3}{2}\times 2+\frac{5}{4}+\frac{3}{4}+\frac{7}{16}+\frac{1}{8}\times 2, \frac{3}{2}+\frac{5}{4}\times 2+\frac{3}{4}+\frac{7}{16}\times 2+\frac{1}{8}, \frac{5}{4}\times 3+\frac{3}{4}+\frac{7}{16}\times 3\}=\frac{3}{16}>0$.

Case 6 $n_{2}(v)=1$. Then $f_3(v)\le 5$. If $f_3(v)=0$, then $c'(v)\ge 8-1-1\times 7=0$. If $f_3(v)=1$, then $f_4(v)\le 4$. So $c'(v)\ge 8-1-\frac{3}{2}-1\times 4-\frac{7}{16}\times 2=\frac{5}{8}>0$. If $f_3(v)=2$, then $f_4(v)\le 4$. If $f_4(v)=4$, then $c'(v)\ge 8-1-\frac{3}{2}\times 2-1\times 2-\frac{2}{3}\times 2-\frac{7}{16}=\frac{11}{48}>0$. If $f_4(v)\le 3$, then $c'(v)\ge 8-1-\frac{3}{2}\times 2-1\times 3-\frac{7}{16}\times 2=\frac{1}{8}>0$. If $f_3(v)=3$, then $f_4(v)\le 2$. If $f_4(v)=2$, then $c'(v)\ge 8-1-\frac{3}{2}\times 2-\frac{5}{4}-1\times 2-\frac{1}{8}\times 2=\frac{1}{2}>0$. If $f_4(v)\le 1$, then $c'(v)\ge 8-1-\frac{3}{2}\times 3-1-\frac{7}{16}\times 3=\frac{3}{16}>0$. If $f_3(v)=4$, then $f_{6^{+}}(v)\ge 2$ or $f_{5^{+}}(v)\ge 3$. So $c'(v)\ge 8-1-max\{\frac{3}{2}\times 4+\frac{1}{8}\times 3, \frac{3}{2}\times 3+\frac{5}{4}+1+\frac{1}{8}\times 2, \frac{3}{2}\times 2+\frac{5}{4}\times 2+1+\frac{1}{8}\times 2\}=0$. If $f_3(v)=5$, then $f_{6^{+}}(v)\ge 2$. So $c'(v)\ge 8-1-\frac{3}{2}-\frac{5}{4}\times 4-\frac{1}{8}\times 2=\frac{1}{4}>0$ by (iv).

Case 7 $n_{2}(v)=0$. Then $f_3(v)\le 5$. If $f_3(v) \le 2$, then $c'(v)\ge 8-\frac{3}{2}\times f_3(v)-1\times [7-f_3(v)]\ge 0$. If $f_3(v)=3$, then $f_4(v)\le 2$. So $c'(v)\ge 8-\frac{3}{2}\times 3-1\times 2-\frac{7}{16}\times 2=\frac{5}{8}>0$. If $f_3(v)=4$, then $f_4(v)\le 1$. So $c'(v)\ge 8-\frac{3}{2}\times 4-1-\frac{7}{16}\times 2=\frac{1}{8}>0$. If $f_3(v)=5$, then $f_{6^{+}}(v)\ge 2$. So $c'(v)\ge 8-\frac{3}{2}\times 5=\frac{1}{2}>0$.

Hence we complete the proof of the theorem.