In this paper, all graphs are considered as finite, simple and undirected planar graphs. Let $V(G)$, $E(G)$, $F(G)$ and $\Delta(G)$ denote the vertex set, the edge set, the face set and the maximum degree of a graph $G$, respectively. Let $|V(G)|$, $|E(G)|$, $|F(G)|$ denote the number of vertices, edges and faces in $G$, respectively. For a vertex $v\in V(G)$, let $N(v)$ denote the set of vertices adjacent to $v$ and $d(v)=|N(v)|$ denote the degree of $v$. A vertex of degree $k$ (resp. at least $k$, at most $k$) is called a $k$-vertex (resp. $k^{+}$-vertex, $k^{-}$-vertex). An edge $uv$ is type $(a, \leq b)$ means $d(u)=a, d(v)\leq b$. For $f\in F(G)$, we write $f=[v_1, \cdots, v_k]$ if $v_1, \ldots, v_k$ are the vertices on the boundary walk in some fixed order. A $k$-face $[v_1, \cdots, v_k]$ is called $(d_1, \cdots, d_k)$ face if $d(v_i)=d_i$, $i=1, \cdots, k$.

For any $V'\subseteq V(G)$, we denote the graph with vertex set $V(G)-V'$ and edge set $\{xy\in E(G): \{x, y\}\subseteq V(G)-V'\}$ by $G-V'$; for any $E'\subseteq E(G)$, we denote the graph with vertex set $V(G)$ and edge set $E(G)-E'$ by $G-E'$. When $V'=\{v\}$, we shall simply write $G-v$. Let $G_{1}$ be a subgraph of $G$ and let $G_{2}\subseteq V(G)\cup E(G)$ be a set such that every edge of $G_{2}$ has both endpoints in $V(G_{1})\cup (G_{2}\cap V(G))$, then we denote the graph with vertex set $V(G_{1})\cup (G_{2} \cap V(G))$ and edge set $E(G_{1})\cup(G_{2}\cap E(G))$ by $G_{1}+G_{2}$.

Acyclic graphs are called forests. A forest whose maximum degree is at most 2 is called a linear forest. The decomposition of a graph $G$ consists of edge-disjoint subgraphs with union $G$. If all the edge-disjoint subgraphs are forests, then we call this decomposition a forest decomposition.

Decompositions of planar graphs were widely studied. In [1], it proved that every planar graph can be decomposed into three forests with one forest whose maximum degree is at most 4. In [2], it proved that a planar graph not containing 4-cycles can be decomposed into a forest and a graph with maximum degree at most 5, which can not be improved to 3. In this paper, we focus on the forest decomposition of planar graphs without 5-cycles or $K_4$.

The purpose of this section is to prove the following result.

Theorem 2.1  Every planar graph without $5$-cycles or $K_4$ can be decomposed into two forests $F_1$, $F_2$ and a linear forest $P$.

Proof  We prove the theorem by reduction to absurdity. Let $G$ be a counter example with $|V(G)|+|E(G)|$ minimum. The following configurations are excluded from $G$. These obvious facts will be frequently used.

($C_01$) A $5$-face;

($C_02$) A $3$-face adjacent to a 4-face;

($C_03$) A $3$-face adjacent to two 3-faces.

Lemma 2.2  $G$ is connected and has no vertex $v$ with $d(v)\leq 2$.

Proof  If $G$ is disconnected, then one of its components is a counter example with fewer vertices, a contradiction. Let $v\in V(G)$ with $d(v)\leq2$. Consider the graph $G':=G-v$, by the choice of $G$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$ and $P'$ with $\Delta(P')\leq2$. When $d(v)=2$, let $u$, $w$ be the other two neighbors of $v$, and $F_1 =F'_1+\{vu\}$, $F_2 =F'_2+\{vw\}$, $P =P'$. When $d(v)=1$, let $u$ be the other neighbor of $v$, and $F_1 =F'_1+\{vu\}$, $F_2 =F'_2$, $P =P'$. It is obvious that $F_1, F_2, P$ are forests and cover $G$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction.

Lemma 2.3  $G$ has no edge $uv$ with $d(u)=3$, $d(v)\leq 4$.

Proof  Suppose $uv$ is such an edge that $d(u)=3$, $d(v)\leq 4$. Let $w_1, \ w_2$ be the other two neighbors of $u$. Consider the graph $G':=G-\{uv, uw_1, uw_2\}$, by the choice of $G$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$ and $P'$ with $\Delta(P')\leq2$. Without loss of generality, we may further assume that the number of edges in $P'$ is minimum. Therefore, for any $w\in V(P')$, $d_{F'_i}(w) \geq1$ for $i=1, \ 2$. Hence, $d_{P'} (w)\leq d_{G'}(w) -2 $ for every vertex $w$ of $G'$. Hence $d_{P'}(u)=0$, $d_{P'}(v)\leq d_{G'}(v)-2=4-1-2=1$. Let $F_1 =F'_1+\{uw_1\}$, $F_2 =F'_2+\{uw_2\}$, $P =P'+\{uv\}$. It is easy to check that $F_1, \ F_2, \ P$ are forests and cover $G$. Note that $d_{P}(u)=d_{P'}(u)+1=1$, $d_{P}(v)=d_{P'}(v)+1\leq2$, and for any other vertex $w\in V(P)-\{u, v\}$, $d_{P}(w)=d_{P'}(w)\leq2$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction.

Lemma 2.4  $G$ has no (3, 5)-alternating cycle.

Proof  Let $C=[v_1v_2\cdots v_{2r}]$ be a (3, 5)-alternating cycle in $G$, i.e., $d(v_i)=3$, for $i=1, 3, \cdots, 2r-1$; and $d(v_i)=5$, for $i=2, 4, \cdots, 2r$. Consider the graph $G':=G-E(C)$, since $|V(G')|+|E(G')|<|V(G)|+|E(G)|$, by the choice of $G$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$ and $P'$ with $\Delta(P')\leq2$. Without loss of generality, we may further assume that the number of edges in $P'$ is minimum. Therefore, for each $u\in V(P')$, $d_{F'_1}(u) \geq1$, $d_{F'_2}(u) \geq1$; for each $u\in G'$, $d_{P'}(u)\leq d_{G'}(u)-2 $. So $d_{P'}(v_i)=0$ when $i=1, 3, \cdots, 2r-1$, $d_{P'}(v_i)\leq 1$ when $i=2, 4, \cdots, 2r$. Let $w_i$ ($i=1, 3, \cdots, 2r-1$) be the other neighbors of $v_i$. What is more, we can assume that $v_iw_i\in F'_1$. Let $F_1 =F'_1$,

$ F_2 =F'_2+\{v_iv_{i+1}, \ i=1, 3, \cdots, 2r-1\}, P =P'+\{v_iv_{i+1}, \ i=2, 4, \cdots, 2r-2\}. $

It is easy to check that $F_1, \ F_2, \ P$ are forests and cover $G$. Note that $d_{P}(v_i)=d_{P'}(v_i)+1=1$, $i=1, 3, \cdots, 2r-1$ and $d_{P}(v_i)=d_{P'}(v_i)+1\leq 2$, $i=2, 4, \cdots, 2r$, for other $u \in V(P)$, $d_P(u)=d_{P'}(u)\leq 2$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction.

Let $d(x)$ denote the size of a face $f$. Since $G$ is a planar graph, by Euler's formula $|V(G)|-|E(G)|+|F(G)| =2$, we have

$ \sum\limits_{v \in V\left( G \right)} {\left( {2d\left( v \right) - 6} \right) + } \sum\limits_{f \in F\left( G \right)} {\left( {d\left( f \right) - 6} \right) = - 6\left( {|V\left( G \right)| - |E\left( G \right)| + |F\left( G \right)|} \right) = - 12} < 0. $

(1)

Define $ch(v)=2d(v)-6$ for each vertex $v\in V(G)$ and $ch(f)=d(f)-6$ for each face $f\in F(G)$ be the initial charges. So the total sum of charges is negative. In the following, we will assign a new charges $ch'(x)$ for each $x\in V(G)\cup F(G)$ according to the discharging rules. Since our rules only move charges around and do not affect the sum, the total sum of charge keep fixed after the discharging is done. So we have

$ \sum\limits_{x \in V\left( G \right) \cup F\left( G \right)} {ch'\left( x \right) = } \sum\limits_{x \in V\left( G \right) \cup F\left( G \right)} {ch\left( x \right) = - 12 < 0.} $

(2)

Let $v\in V(G)$ with $d(v)=6$. We say that $v$ is weak of type 1, if $v$ is incident to four 3-faces, denote by $6_1$; we say $v$ is strong of type 1, if $v$ is incident to at least one 3-face and incidents to at most three 3-faces. $v$ is weak of type 2, if $v$ is incident to six 4-faces and all the neighbors of $v$ are 3-vertices, denote by $6_2$; otherwise, i.e. $v$ is incident to at least one 3-face and at most five 4-faces or $v$ is incident to six 4-faces, but at least one neighbor is not 3-vertex, then we call it strong of type 2. Let $n_\triangle (v)$ (resp. $n_\Box (v)$) denote the number of the 3-faces (resp. 4-faces) incident to $v$. The vertices and faces of $G$ discharge their initial charges by the following rules:

R 1  Let $f=[v_1v_2v_3]$ be a 3-face.

R 1.1 $d(v_1)=3$, $d(v_2)=d(v_3)=5$ or $d(v_1)=3$, $d(v_2)\geq 6$, $d(v_3)\geq 6$, $f$ gets $\frac{3}{2}$ from $v_2, \ v_3, $ respectively.

R 1.2 $d(v_1)=3$, $d(v_2)=5$, $d(v_3)=6$, if $v_3$ is weak of type 1, $f$ gets $\frac{3}{2}$ from $v_2, \ v_3$ respectively; if $v_3$ is strong of type 1 or $d(v_3)\geq 7$, $f$ gets 1 from $v_2$, gets 2 from $v_3$.

R 1.3 $d(v_1)\geq 4$, $d(v_2)\geq 4$, $d(v_3)\geq 4$, $f$ gets 1 from each incidenting vertex.

R 2  Let $f=[v_1v_2v_3v_4]$ be a 4-face.

R 2.1 $d(v_1)=3$, $(v_2)=5$, $d(v_3)=3$, $d(v_4)=6$, if $v_4$ is weak of type 2, $f$ gets 1 from $v_2, \ v_4$ respectively; if $v_4$ is strong of type 2, $f$ gets $\frac{2}{3}$ from $v_2$, gets $\frac{4}{3}$ from $v_4$.

R 2.2 $d(v_1)=3$, $(v_2)=5$, $d(v_3)=3$, $d(v_4)\geq 7$, $f$ gets $\frac{2}{3}$ from $v_2$, gets $\frac{4}{3}$ from $v_4$.

R 2.3 $d(v_1)=3$, $(v_2)\geq 6$, $d(v_3)=3$, $d(v_4)\geq6$, $f$ gets 1 from $v_2, \ v_4, $ respectively.

R 2.4 $d(v_1)=3$, $(v_2)=5$, $d(v_3)=4$, $d(v_4)=5$, or $d(v_1)=3$, $(v_2)\geq6$, $d(v_3)=4$, $d(v_4)\geq6$, $f$ gets $\frac{3}{4}$ from $v_2, \ v_4, $ respectively, gets $\frac{1}{2}$ from $v_3$.

R 2.5 $d(v_1)=3$, $(v_2)=5$, $d(v_3)=4$, $d(v_4)\geq 6$, $f$ gets $\frac{7}{12}$ from $v_2$, gets $\frac{1}{2}$ from $v_3$, gets $\frac{11}{12}$ from $v_4$.

R 2.6 $d(v_1)=3$, $(v_2)\geq5$, $d(v_3)\geq 5$, $d(v_4)\geq 5$, $f$ gets $\frac{2}{3}$ from $v_2, \ v_3, \ v_4, $ respectively.

R 2.7 $d(v_1)\geq4$, $(v_2)\geq4$, $d(v_3)\geq 4$, $d(v_4)\geq 4$, $f$ gets $\frac{1}{2}$ from each adjacent vertex.

In the rest of the paper, we show that the final charge $ch'(x)$ is nonnegative for each $x\in V(G)\cup F(G)$, which is a contradiction to formula (2), then we can complete the proof.

From the discharging rules, it is obvious that $ch'(f)\geq0$ for arbitrary $f\in F(G)$. Next we consider $v\in V(G)$, let $d(v)=d$. By Lemma 2.2, we know $d\geq3$.

Case 1  $d=3.$

For arbitrary 3-vertex $v$, it is obvious that $ch'(v)=ch(v)=2\times3-6=0$.

Case 2  $d=4.$

When $n_\triangle (v)=0$, then $n_\Box (v)\leq 4$, we have $ch'(v)\geq 2\times4-6-4\times\frac{1}{2}=0$ by R 2.4, R 2.5, R 2.7. When $n_\triangle (v)=1$, then $n_\Box (v)\leq 1$, we have $ch'(v)\geq 2\times4-6-(1+\frac{1}{2})=\frac{1}{2}\geq 0$ by R 1.3, R 2.4, R 2.5, R 2.7. When $n_\triangle (v)=2$, then $n_\Box (v)=0$, we have $ch'(v)\geq 2\times4-6-2\times1=0$ by R 1.3.

Case 3  $d=5.$

Let $v_1, v_2, \cdots, v_5$ be the neighbors of $v$ in the clock direction.

Case 3.1  $n_\triangle (v)=0.$

If $n_\Box (v)\leq 4$, then $ch'(v)\geq 2\times5-6-4\times1=0$ by R 2. Now we assume $n_\Box (v)=5$. Denote the five 4-faces incident to $v$ by $f_i=[v v_i w_i v_{i+1}]$, $i=1, \cdots, 5.$

Lemma 2.5  The type of $(5, \ 3, \ 6_2, \ 3)$ 4-faces are not incident to each other. Therefore, at most two $(5, 3, 6_2, 3)$ 4-faces are incident to $v$.

Proof  Let $f_1=[vv_1w_1v_2]$, $f_2=[vv_2w_2v_3]$, $d(w_1)=d(w_2)=6$, and $w_1$, $w_2$ are weak of type 2, then $w_1$, $v_2$, $w_2$ must be contained in one 4-face, denote by $f_3=[w_1v_2w_2x]$. What is more, $d(x)=3$. Consider the graph $G':=G-E(f_1)-E(f_2)-E(f_3)$, since $|V(G')|+|E(G')|<|V(G)|+|E(G)|$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$ and $P'$ with $\Delta(P')\leq2$. Without loss of generality, we may further assume that the number of edges in $P'$ is minimum. Therefore, for any $u\in V(P')$, $d_{F'_i}(u) \geq1$ for $i=1, 2$, and $d_{P'} (u)\leq d_{G'}(u)-2 $. Then we get $d_{P'}(v)=0$, $d_{P'}(v_1)=0$, $d_{P'}(w_1)\leq 1$, $d_{P'}(v_2)=0$, $d_{P'}(w_2)\leq 1$, $d_{P'}(v_3)=0$, $d_{P'}(x)=0$. We can further assume that the edges incident to $v_1, \ v_3, \ x$ in $G'$ are in $F'_1$. Let $F_1 =F'_1+ \{w_1v_2\}$, $F_2 =F'_2+ \{vv_3, \ v_1w_1, \ v_2w_2, \ w_2x\}$, $P =P'+\{vv_1, \ vv_2, \ w_1x, \ w_2v_3\}$. It is easy to check that $F_1, \ F_2, \ P$ are forests and cover $G$. And

$ d_P(v)=d_{P'}(v)+2=2, d_P(v_1)=d_{P'}(v_1)+1=1, \\ d_P(w_1)=d_{P'}(w_1)+ 1\leq 2, d_P(v_2)=d_{P'}(v_2)+1=1, \\ d_P(w_2)=d_{P'}(w_2)+1\leq 2, d_P(v_3)=d_{P'}(v_3)+1=1, \\ d_P(x)=d_{P'}(x)+1=1 $

for other $u \in V(P)$, $d_P(u)=d_{P'}(u)\leq 2$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction.

If there is no $(5, 4, 5, 3)$ 4-face incident to $v$, then $ch'(v)\geq 2\times5-6-(1\times2+\frac{2}{3}\times 3)=0$ by R 2. Now we assume that there is at least one $(5, 4, 5, 3)$ 4-face incident to $v$. Let $f_1$ be such a 4-face and suppose $d(v_1)=3$, $d(w_1)=5$, $d(v_2)=4$.

Lemma 2.6  $d(w_2)\geq 6$ or $d(v_3)\neq 3$. Both cases we can get $ch'(x)\geq 0$.

Proof  Suppose $d(w_2)=5$ and $d(v_3)=3$, Consider the graph $G':=G-E(f_1)-E(f_2)$. Since $|V(G')|+|E(G')|<|V(G)|+|E(G)|$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$ and $P'$ with $\Delta(P')\leq2$. Without loss of generality, we may further assume that the number of edges in $P'$ is minimum. Then we get $d_{P'}(v)=0$, $d_{P'}(v_1)=0$, $d_{P'}(w_1)\leq 1$, $d_{P'}(v_2)=0$, $d_{P'}(w_2)\leq 1$, $d_{P'}(v_3)=0$. We can further assume that the edges incident to $v_1$, $v_2$, $v_3$ in $G'$ are in $F'_1$. Let $F_1 =F'_1$, $F_2 =F'_2+ \{vv_1, w_1v_2, w_2v_3\}$, $P =P'+\{vv_2, vv_3, v_1w_1, v_2w_2\}$. It is easy to check that $F_1, F_2, P$ are forests and cover $G$. And

$ d_P(v)=d_{P'}(v)+2=2, d_P(v_1)=d_{P'}(v_1)+1=1, d_P(w_1)=d_{P'}(w_1)+1\leq 2, \\ d_P(v_2)=d_{P'}(v_2)+2=2, d_P(w_2)=d_{P'}(w_2)+1\leq 2, \\ d_P(v_3)=d_{P'}(v_3)+1=1 $

for other $u \in V(P)$, $d_P(u)=d_{P'}(u)\leq 2$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction. So $d(v_2)\geq6$ or $d(v_2)\neq3$.

If $d(w_2)\geq 6$, then

$ ch'(v)\geq 2\times5-6-(\frac{3}{4}+\frac{7}{12}+1\times 2+\frac{2}{3})=0 $

by R 2; if $d(v_3)\neq 3$, then $ch'(v)\geq 2\times5-6-(\frac{3}{4}+\frac{1}{2}+1\times 2+\frac{2}{3})>0$ by R 2.

Case 3.2  $n_\triangle (v)=1.$

$n_\Box(v)\leq 2$, so $ch'(v)\geq 2\times5-6-(\frac{3}{2}+1\times 2)=\frac{1}{2}\geq 0$ by R 1, R 2.

Case 3.3  $n_\triangle (v)=2.$

$n_\Box(v)\leq 1$, so $ch'(v)\geq 2\times5-6-(\frac{3}{2}\times2+1)= 0$ by R 1, R 2.

Case 3.4  $n_\triangle (v)=3.$

Let $f_1=[vv_1v_2]$, $f_2=[vv_2v_3]$, $f_3=[vv_4v_5]$ denote the three 3-faces. If there exists one 3-face that does not contain any 3-vertex, then $ch'(v)\geq 2\times5-6-(\frac{3}{2}\times2+1)= 0$ by R 1. Now we assume that all three 3-faces contain a 3-vertex, then there are two configurations to consider.

(C1) $d(v_1)=d(v_3)=d(v_5)=3$;

(C2) $d(v_2)=d(v_5)=3$.

Lemma 2.7  For (C1), $d(v_2)\geq 7$, $ch'(v)>0$.

Proof  Suppose $d(v_2)\leq 6$, Consider the graph $G':=G-E(f_1)-E(f_2)-E(f_3)$, since $|V(G')|+|E(G')|<|V(G)|+|E(G)|$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$ and $P'$ with $\Delta(P')\leq2$. Without loss of generality, we may further assume that the number of edges in $P'$ is minimum. Then we get $d_{P'}(v)=0$, $d_{P'}(v_1)=0$, $d_{P'}(v_2)\leq 1$, $d_{P'}(v_3)=0$, $d_{P'}(v_5)=0$. We can further assume that the edges incident to $v_1$, $v_3$, $v_5$ in $G'$ are in $F'_1$. Let $F_1 =F'_1+ \{vv_2\}$, $F_2 =F'_2+ \{vv_1, vv_4, v_2v_3, v_4v_5\}$, $P =P'+\{vv_3, vv_5, v_1v_2\}$. It is easy to check that $F_1, F_2, P$ are forests and cover $G$. And $d_P(v)=2$, $d_P(v_1)=1$, $d_P(v_2)\leq 2$, $d_P(v_3)=1$, $d_P(v_5)=1$, for other $u \in V(P)$, $d_P(u)=d_{P'}(u)\leq 2$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction. So $d(v_2)\geq7$ and $ch'(v)\geq2\times5-6-(1\times2+\frac{2}{3})>0$ by R1.

Lemma 2.8  For (C2), $ch'(v)\geq0$.

Proof  When $d(v_4)=5$, if $d(v_1)\geq6$ and $d(v_3)\geq6$, since $v_1$, $v_3$ cannot be 6-vertices and weak of type 1 by $(C_03)$, $ch'(v)\geq2\times5-6-(1\times2+\frac{3}{2})>0$ by R 1. Otherwise, by symmetry, suppose $d(v_1)=5$. Consider the graph $G':=G-E(f_1)-E(f_2)-E(f_3)$, since $|V(G')|+|E(G')|<|V(G)|+|E(G)|$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$, $P'$ with $\Delta(P')\leq2$. Without loss of generality, we may further assume that the number of edges in $P'$ is minimum. Then we get that $d_{P'}(v)=0$, $d_{P'}(v_1)\leq 1$, $d_{P'}(v_2)=0$, $d_{P'}(v_4)\leq 1$, $d_{P'}(v_5)=0$. We can further assume that the edges incident to $v_5$ in $G'$ are in $F'_1$. Let $F_1 =F'_1+ \{vv_3, \ v_2v_3\}$, $F_2 =F'_2+ \{vv_1, \ vv_2, \ v_4v_5\}$, $P =P'+\{vv_4, \ vv_5, \ v_1v_2\}$. It is easy to check that $F_1, \ F_2, \ P$ are forests and cover $G$. And $d_P(v)=2$, $d_P(v_1)\leq 2$, $d_P(v_2)=1$, $d_P(v_4)\leq 2$, $d_P(v_5)=1$, for other $u \in V(P)$, $d_P(u)=d_{P'}(u)\leq 2$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction.

When $d(v_4)\geq 6$, if $v_1$, $v_3$ can not be 5-vertices in the same time, then

$ ch'(v)\geq2\times5-6-(1+\frac{3}{2}\times 2)=0 $

by R 1. Otherwise, suppose $d(v_1)=5, \ d(v_3)=5$. Consider the graph

$ G':=G-E(f_1)-E(f_2)-E(f_3), $

since $|V(G')|+|E(G')|<|V(G)|+|E(G)|$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$ and $P'$ with $\Delta(P')\leq2$. Without loss of generality, we may further assume that the number of edges in $P'$ is minimum. Then we get that $d_{P'}(v)=0$, $d_{P'}(v_1)\leq 1$, $d_{P'}(v_2)=0$, $d_{P'}(v_3)\leq 1$, $d_{P'}(v_5)=0$. We can further assume that the edges incident to $v_5$ in $G'$ are in $F'_1$. Let $F_1 =F'_1+ \{vv_4, \ v_2v_3\}$, $F_2 =F'_2+ \{vv_1, \ vv_2, \ v_4v_5\}$, $P =P'+\{vv_3, \ vv_5, \ v_1v_2\}$. It is easy to check that $F_1, \ F_2, \ P$ are forests and cover $G$. And $d_P(v)=2$, $d_P(v_1)\leq 2$, $d_P(v_2)=1$, $d_P(v_3)\leq 2$, $d_P(v_5)=1$, for other $u \in V(P)$, $d_P(u)=d_{P'}(u)\leq 2$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction.

Case 4  $d=6.$

Let $v_1, v_2, \cdots, \ v_6$ be the neighbors of $v$ in the clock direction. If $v$ is weak of type 2, then $ch'(v)=2\times6-6-1\times 6=0$ by R 2.1. Now suppose $v$ is strong of type 2.

Lemma 2.9  There is at most one $(6, 3, 5, 3)$ $4$-face incidenting to $v$.

Proof  Suppose that there are two $(6, 3, 5, 3)$ 4-faces $f_1, \ f_2$ incident to $v$, let

$ f_1=[vv_1w_1v_2], $

by symmetry, there are three cases to consider, $f_2=[vv_2w_2v_3]$ or $f_2=[vv_3w_3v_4]$ or

$ f_2=[vv_4w_4v_5]. $

Case 2.9.1  $f_2=[vv_2w_2v_3]$.

Consider the graph $G':=G-E(f_1)-E(f_2)$, since $|V(G')|+|E(G')|<|V(G)|+|E(G)|$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$, $P'$ with $\Delta(P')\leq2$. Without loss of generality, we may further assume that the number of edges in $P'$ is minimum. Then we get that $d_{P'}(v)\leq 1$, $d_{P'}(v_1)=0$, $d_{P'}(w_1)\leq 1$, $d_{P'}(v_2)=0$, $d_{P'}(w_2)\leq 1$, $d_{P'}(v_3)=0$. What is more, we can assume that the edges incident to $v_1, \ v_3$ in $G'$ are in $F'_1$. Let $F_1 =F'_1 + \{vv_2\}$, $F_2 =F'_2+ \{vv_1, \ w_1v_2, \ w_2v_3\}$, $P =P'+\{vv_3, \ v_1w_1, \ v_2w_2\}$. It is easy to check that $F_1, \ F_2, \ P$ are forests and cover $G$. And

$ d_P(v)\leq d_{P'}(v)+1\leq 2, d_P(v_1)=d_{P'}(v_1)+1=1, \\ d_P(w_1)\leq d_{P'}(w_1)+1\leq 2, d_P(v_2)=d_{P'}(v_2)+1=1, \\ d_P(w_2)\leq d_{P'}(w_2)+1\leq 2, d_P(v_3)=d_{P'}(v_3)+1=1 $

for other $u \in V(P)$, $d_P(u)=d_{P'}(u)\leq 2$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction.

Case 2.9.2  $f_2=[vv_3w_3v_4]$.

Consider the graph $G':=G-E(f_1)-E(f_2)$, since $|V(G')|+|E(G')|<|V(G)|+|E(G)|$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$ and $P'$ with $\Delta(P')\leq2$. Without loss of generality, we may further assume that the number of edges in $P'$ is minimum. Then we get that $d_{P'}(v)\leq 1$, $d_{P'}(v_1)=0$, $d_{P'}(w_1)\leq 1$, $d_{P'}(v_2)=0$, $d_{P'}(v_3)=0$, $d_{P'}(w_3)\leq 1$, $d_{P'}(v_4)=0$. What is more, we can assume that the edges incident to $v_1$, $v_2$, $v_3$, $v_4$ in $G'$ are in $F'_1$. Let $F_1 =F'_1 $, $F_2 =F'_2+ \{vv_1, vv_4, w_1v_2, v_3w_3, \}$, $P =P'+\{vv_2, vv_3, v_1w_1, w_3v_4\}$. It is easy to check that $F_1, F_2, P$ are forests and cover $G$. And

$ d_P(v)=d_{P'}(v)+2=2, d_P(v_1)=d_{P'}(v_1)+1=1, \\ d_P(w_1)\leq d_{P'}(w_1)+1\leq 2, d_P(v_2)=d_{P'}(v_2)+1=1, \\ d_P(v_3)=d_{P'}(v_3)+1=1, d_P(w_3)\leq d_{P'}(w_3)+1\leq 2, \\ d_P(v_4)=d_{P'}(v_4)+1=1 $

for other $u \in V(P)$, $d_P(u)=d_{P'}(u)\leq 2$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction.

Case 2.9.3 $f_2=[vv_4w_4v_5]$.

Consider the graph $G':=G-E(f_1)-E(f_2)$, since $|V(G')|+|E(G')|<|V(G)|+|E(G)|$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$, $P'$ with $\Delta(P')\leq2$. Without loss of generality, we may further assume that the number of edges in $P'$ is minimum. Then we get that $d_{P'}(v)=0$, $d_{P'}(v_1)=0$, $d_{P'}(w_1)\leq 1$, $d_{P'}(v_2)=0$, $d_{P'}(v_4)=0$, $d_{P'}(w_4)\leq 1$, $d_{P'}(v_5)=0$. What is more, we can assume that the edges incident to $v_1, \ v_2, \ v_4, \ v_5$ in $G'$ are in $F'_1$. Let $F_1 =F'_1 $, $F_2 =F'_2+ \{vv_1, \ vv_4, \ w_1v_2, \ w_4v_5\}$, $P =P'+\{vv_2, \ vv_5, \ v_1w_1, \ v_4w_4\}$. It is easy to check that $F_1, \ F_2, \ P$ are forests and cover $G$. And

$ d_P(v)=d_{P'}(v)+2=2, d_P(v_1)=d_{P'}(v_1)+1=1, \\ d_P(w_1)\leq d_{P'}(w_1)+1\leq 2, d_P(v_2)=d_{P'}(v_2)+1=1, \\ d_P(v_4)=d_{P'}(v_4)+1=1, d_P(w_4)\leq d_{P'}(w_4)+1\leq 2, \\ d_P(v_5)=d_{P'}(v_5)+1=1 $

for other $u \in V(P)$, $d_P(u)=d_{P'}(u)\leq 2$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction.

Case 4.1  $n_\triangle (v)=0.$

If $n_\Box (v)\leq5$, then $ch'(v)\geq 2\times6-6-(4+\frac{4}{3})>0$ by R 2. Now suppose $n_\Box (v)=6$, if there is no $(6, \ 3, \ 5, \ 3)$ 4-face incident to $v$, then $ch'(v)\geq 2\times6-6-1\times 6=0$ by R 2. There must be one $(6, \ 3, \ 5, \ 3)$ 4-face incident to $v$, if there is one 4-face which are not incident to a 3-vertex, then $ch'(v)\geq 2\times6-6-(\frac{4}{3}+\frac{1}{2}+1\times 4)>0$ by R 2. Now suppose $f_1=[vv_1w_1v_2]$ is a $(6, \ 3, \ 5, \ 3)$ 4-face, and all 4-faces incident to $v$ contain a 3-vertex, if $d(w_3)=3$ or $d(w_4)=3$ or $d(w_5)=3$, then

$ ch'(v)\geq 2\times6-6-(\frac{4}{3}+\frac{2}{3}+1\times 4)=0 $

by R 2. So we assume $d(w_3)\geq 4$, $d(w_4)\geq 4$, $d(w_5)\geq4$. Since every four face is incident to 3-vertex, there are at least two vertices of $v_3, \ v_4, \ v_5, \ v_6$ be 3-vertices, at least one is non 3-vertices, we assume that $d(v_4)=3, d(v_6)=3$ (the other cases are similar). If $d(v_3)\geq 5$ or $d(v_5)\geq 5$, then

$ ch'(v)\geq 2\times6-6-(\frac{4}{3}+1+\frac{2}{3}\times 2+1\times 2)>0 $

by R 2; if $d(v_3)=4$ and $d(v_5)=4$ then

$ ch'(v)\geq 2\times6-6-(\frac{4}{3}+1+\frac{11}{12}\times4)=0 $

by R 2; if $d(v_3)=3$ and $d(v_5)=4$, then if $d(w_4)\geq 6$ or $d(w_5)\geq 6$, we have

$ ch'(v)\geq 2\times6-6-(\frac{4}{3}+1\times 3+\frac{3}{4}+\frac{11}{12})=0 $

by R 2. So we assume $d(v_3)=3$, $d(v_5)=4$, $d(w_4)=5$ and $d(w_5)=5$, then we consider the graph $G':=G-E(f_1)-\cdots-E(f_6)$, since $|V(G')|+|E(G')|<|V(G)|+|E(G)|$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$, $P'$ with $\Delta(P')\leq2$. Without loss of generality, we may further assume that the number of edges in $P'$ is minimum. Then we get that $d_{P'}(v)=0$, $d_{P'}(v_1)=0$, $d_{P'}(w_1)\leq 1$, $d_{P'}(v_2)=0$, $d_{P'}(v_3)=0$, $d_{P'}(v_4)=0$, $d_{P'}(w_4)\leq 1$, $d_{P'}(v_5)=0$, $d_{P'}(w_5)\leq 1$, $d_{P'}(v_6)=0$, what is more, we can assume that the edges incident with $v_5$ in $G'$ are in $F'_1$. Let $F_1 =F'_1+ \{vv_4, \ w_1v_2, \ w_2v_3, \ w_3v_4, \ v_6w_6\} $, $F_2 =F'_2+\{vv_1, \ vv_5, \ vv_6\}$, $P =P'+\{vv_2, \ vv_3, \ v_1w_1, \ w_4v_5, \ w_5v_6\}$. It is easy to check that $F_1, F_2, \ P$ are forests and cover $G$. And

$ d_P(v)=d_{P'}(v)+2=2, d_P(v_1)=d_{P'}(v_1)+1=1, \\ d_P(w_1)=d_{P'}(w_1)+1\leq2, d_P(v_2)=d_{P'}(v_2)+1=1, \\ d_P(v_3)=d_{P'}(v_3)+1=1, d_P(v_4)=d_{P'}(v_4)+1=1, \\ d_P(w_4)=d_{P'}(w_4)+1\leq 2, d_P(v_5)=d_{P'}(v_5)+1=1, \\ d_P(w_5)=d_{P'}(w_5)+1\leq 2, d_P(v_6)=d_{P'}(v_6)+1=1 $

for other $u \in V(P)$, $d_P(u)=d_{P'}(u)\leq 2$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction.

Case 4.2  $n_\triangle (v)=1.$

There are at most three 4-faces incident to $v$, and at most one of the three 4-faces is $(6, \ 3, \ 5, \ 3)$ 4-face, so $ch'(v)\geq 2\times6-6-(2+\frac{4}{3}+1\times 2)>0$ R 1, R 2.

Case 4.3  $n_\triangle (v)=2.$

When $n_\Box(v)\leq1$, then $ch'(x)\geq 2\times6-6-(2\times 2+\frac{4}{3})>0$ by R 1, R 2; when $n_\Box(v)=2$, let $f_1=[vv_1v_2]$, $f_2=[vv_2v_3]$, $f_3=[vv_4w_4v_5]$, $f_4=[vv_5w_5v_6]$. If $d(w_4)\geq6$, $d(w_5)\geq6$, then $ch'(v)\geq 2\times6-6-(2\times 1+2\times2)=0$ by R 1, R 2. So we assume that $d(w_5)=5$, by Lemma 2.9, $d(w_4)\geq6$, if $f_1$ or $f_2$ does not contain a 3-vertex, then $ch'(v)\geq 2\times6-6-(\frac{4}{3}+1+2+\frac{3}{2})>0$ by R 1, R 2. Now we assume that both $f_1$ and $f_2$ contain a 3-vertex, then there are two configurations to consider

(C1) $d(v_1)=d(v_3)=3$;

(C2) $d(v_2)=3$.

Lemma 2.10  For (C1), $d(v_2)\geq6$, so $ch'(v)\geq 0$.

Proof  If it is not true, then by Lemma 2.3, assume $d(v_2)=5$. Consider the graph

$ G':=G-E(f_1)-E(f_2)-E(f_3)-E(f_4), $

since $G'$ has fewer edges than $G$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$ and $P'$ with $\Delta(P')\leq2$. Without loss of generality, we may further assume that the number of edges in $P'$ is minimum. Then we get that $d_{P'}(v)=0$, $d_{P'}(v_1)=0$, $d_{P'}(v_2)=0$, $d_{P'}(v_3)=0$, $d_{P'}(v_4)=0$, $d_{P'}(v_5)=0$, $d_{P'}(w_5)\leq 1$, $d_{P'}(v_6)=0$, what is more, we can assume that the edges incident to $v_1, v_3, v_4, v_6$ in $G'$ are in $F'_1$. Let $F_1 =F'_1+ \{vv_1, vv_6, v_4w_4, v_5w_5\} $, $F_2 =F'_2+ \{vv_2, vv_3, v_1v_2, w_4v_5\}$, $P =P'+\{vv_4, vv_5, v_2v_3, w_5v_6\}$. It is easy to check that $F_1, F_2, P$ are forests and cover $G$. And

$ d_P(v)=d_{P'}(v)+2=2, d_P(v_1)=d_{P'}(v_1)=0, \\ d_P(v_2)=d_{P'}(v_2)+1=1, d_P(v_3)=d_{P'}(v_3)+1=1, \\ d_P(v_4)=d_{P'}(v_4)+1=1, d_P(v_5)=d_{P'}(v_5)+1=1, \\ d_P(w_5)=d_{P'}(w_5)+1\leq 2, d_{P'}(v_6)=d_{P'}(v_6)+1=1 $

for other $u \in V(P)$, $d_P(u)=d_{P'}(u)\leq 2$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction. So $d(v_2)\geq6$,

$ ch'(v)\geq 2\times6-6-(\frac{3}{2}\times 2+\frac{4}{3}+1)>0 $

by R 1, R 2.

Lemma 2.11  For (C2), at least one of $v_{1}, v_{2}$ is a $6^{+}$-vertex, So $ch'(v)>0$.

Proof  If it is not true, then by Lemma 2.3, $d(v_1)=d(v_{3})=5$. Consider the graph $G':=G-E(f_1)-E(f_2)-E(f_3)-E(f_4)$, then $G'$ has fewer edges since $G$, $G'$ can be decomposed into three forests $F'_1$, $F'_2$ and $P'$ with $\Delta(P')\leq2$. Without loss of generality, we may further assume that the number of edges in $P'$ is minimum. Then we get that $d_{P'}(v)=0$, $d_{P'}(v_1)\leq1$, $d_{P'}(v_2)=0$, $d_{P'}(v_3)\leq1$, $d_{P'}(v_4)=0$, $d_{P'}(v_5)=0$, $d_{P'}(w_5)\leq 1$, $d_{P'}(v_6)=0$. What is more, we can assume that the edges incident to $v_4, \ v_6$ in $G'$ are in $F'_1$. Let $F_1 =F'_1+ \{vv_2, vv_5, vv_6\} $,

$ F_2 =F'_2+ \{vv_3, v_1v_2, v_4w_4, w_4v_5, w_5v_6\}, P =P'+\{vv_1, vv_4, v_2v_3, v_5w_5\}. $

It is easy to check that $F_1, F_2, P$ are forests and cover $G$. And

$ d_P(v)=d_P'(v)+2=2, d_P(v_1)=d_{P'}(v_1)+1\leq2, \\ d_P(v_2)=d_{P'}(v_2)+1=1, d_P(v_3)=d_{P'}(v_3)+1\leq2, \\ d_P(v_4)=d_{P'}(v_4)+1=1, d_P(v_5)=d_{P'}(v_5)+1=1, \\ d_P(w_5)=d_{P'}(w_5)+1\leq 2, d_{P'}(v_6)=d_{P'}(v_6)+1=1 $

for other $u \in V(P)$, $d_P(u)=d_{P'}(u)\leq 2$. So $\Delta(P)\leq2$, $\{F_1, F_2, P\}$ is a required decomposition of $G$, a contradiction. Therefore, $d(v_1)\geq6$ or $d(v_3)\geq 6$,

$ ch'(v)\geq 2\times6-6-(\frac{4}{3}+ 2+1+\frac{3}{2})>0 $

by R 1, R 2.

Case 4.4  $n_\triangle (v)=3.$

When $n_\triangle (v)=3$, there is no 4-faces incident to $v$, so $ch'(v)\geq 2\times6-6-2\times 3=0$ by R 1.

Case 4.5  $n_\triangle (v)=4.$

When $n_\triangle (v)=4$, $v$ is weak of type 2, so $ch'(v)\geq 2\times6-6-\frac{3}{2}\times 4=0$ by R 1.

Case 5  $d\geq7.$

When $n_\triangle (v)=0$, the number of $(v, 3, 5, 3)$ 4-faces incident to $v$ is at most $d(v)-4$, the proof is similar to the case for 6-vertex, then

$ ch'(v)\geq 2\times d(v)-6-(\frac{4}{3}\times(d(v)-4)+1\times4)\geq0 $

by R 2. When $0<n_\triangle (v)<\lfloor\frac{2}{3}d(v)\rfloor$,

$ ch'(v)\geq 2\times d(v)-6-(2\times n_\triangle (v)+\frac{4}{3}\times (d(v)-n_\triangle (v)-2))\geq0 $

by R 1, R 2. When $n_\triangle (v)=\lfloor\frac{2}{3}d(v)\rfloor$, $ch'(v)\geq 2\times d(v)-6-2\times n_\triangle (v)\geq0$ by R 1.

In all the cases, for arbitrary $x\in V(G)\cup F(G)$, we get $ch'(x)\geq0$, a contradiction.