# Planar Graphs of Maximum Degree 6 and without Adjacent 8-Cycles Are 6-Edge-Colorable

Authors: Wenwen Zhang
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this paper, by applying the discharging method, we show that ifG is a planar graph with a maximum degree of Δ=6 that does not contain any adjacent 8-cycles, then G is of class 1.


---

## Body

## 1. Introduction

Graph coloring is a very important problem in graph theory. Since the four-color problem was first proposed, many other forms of coloring problems have been put forward and extensively studied. In this paper, we study the edge coloring of a planar graph. It is assumed that all graphs are finite, without parallel edges, and all edges are undirected. Aplanar graph is a graph that can be embedded in the plane satisfying the condition that no two edges intersect geometrically except at a vertex to which they are both incident. Table 1 presents some symbols and definitions used in this paper.Table 1
Symbols of graphs.
EvThe set of all edges incident withvdvCardinality ofEvNvNeighbor set ofvNu,vNu∪NvNNuw|vw∈E,v∈NuNNu,vNNu∪NNvk-, k−-, k+-vertex vVertex withdv=k, dv≤k, or dv≥kk-, k+-neighbor of a vertex xk- or k+-vertex adjacent to xk-cycleCycle of lengthkFGThe set of all faces of a planar graphGdGfNumber of edges onf with each cut edge calculated twicek-, k+-faceFace withdf=k, df≥kmkvNumber ofk-faces incident with vdkvNumber ofk-neighbors of vδixi-th smallest degree of a neighbor of xgLength of the shortest cycle of a graphA graphG is said to be k-edge-colorable if the edges of G can be colored with k colors such that adjacent edges have different colors. In all edge colorings of G, the edge chromatic numberχ′G of a graph G is the minimum number of colors used. In 1964, Vizing proved that, for any graph G of maximum degree Δ, χ′G=ΔG or χ′G=ΔG+1. This result divides all graphs into two classes: graphs G satisfying χ′G=Δ are in class 1, whereas graphs G satisfying χ′G=Δ+1 are in class 2. For a connected graph G, if it is of class 2 and χ′G−e<χ′G for e∈EG, then G is critical. A Δ-critical graph is a critical graph of maximum degree Δ.For planar graphs, Vizing [1] proved that any planar graph with Δ≥8 is of class 1 and illustrated that there are class 2 planar graphs with Δ∈2,3,4,5. Therefore, Vizing conjectured that any planar graph with Δ∈6,7 is of class 1. Zhang [2] and Sanders and Zhao [3] proved the case of Δ=7 independently. The case of Δ=6 has not yet been solved, but some positive results with restrictive conditions have been obtained, as in Theorem 1.Theorem 1.
IfG is one of the following planar graphs, then G is of class 1:(1)
Δ≥3 and g≥8, or Δ≥4 and g≥5, or Δ≥5 and g≥4 ([1])(2)
Δ≥6 without intersecting 3-cycles ([4])(3)
Δ≥6 without 4- or 5-cycles ([5])(4)
Δ≥6 without 5- or 6-cycles with chords [6](5)
Δ≥6 without 5-cycles ([7]) or 6-cycles ([8]) with two chords(6)
Δ≥6 without 7-cycles ([9]) or 6-cycles ([10]) with three chords(7)
Δ≥6 and any vertex is incident with at most three triangles ([11])(8)
Δ≥6 and without adjacent k-cycles, where 3≤k≤6 ([12])(9)
Δ≥6 and any two 7-cycles are not adjacent ([13]).In this paper, two cycles sharing at least a common edge are said to beadjacent. We present a result concerning the edge chromatic number of planar graphs with Δ=6 which do not contain any adjacent 8-cycles.


## 2. Main Result and Its Proof

To prove our main result, we first present several lemmas.Lemma 1 (see [2, 3]).
Suppose thatG is a planar graph with ΔG≥7. Then, χ′G=ΔG.Lemma 2 (Vizing’s Adjacency Lemma [1]).
LetG be a Δ-critical graph, and let uv∈EG with dv=k.(1)
Ifk<Δ, then u has at least Δ−k+1Δ-neighbors(2)
Ifk=Δ, then u has at least two Δ-neighborsLemma 3 (see [2]).
LetG be a Δ-critical graph, and let uv∈EG with du+dv=Δ+2. Then,(1)
Every vertex ofNu,v\u,v is a Δ-vertex(2)
Every vertex ofNNu,v\u,v has a degree of at least Δ−1(3)
Ifdu,dv<Δ, then every vertex of NNu,v\u,v is a Δ-vertexLemma 4 (see [3]).
NoΔ-critical graph has distinct vertices x, y, and z such that x is adjacent to y and z, dz<2Δ−dx−dy+2, and xz is in at least dx+dy−Δ−2 triangles not containing y.We usex,y,z to denote a 3-face with three vertices x,y,z satisfying dx≤dy≤dz. A face f=w,v,x,y is denoted by a bad 4-face in the event that dx=2 and v,x,y form a 3-face. Let ms4v denote the number of bad 4-faces incident with v such that v is incident with a bad 4-face f=v,w,x,y with dx=2. Let m34v=m3v+ms4v, so that m34v≤6.Lemma 5.
LetG be a 6-critical plane graph with no two adjacent 8-cycles. Let dv=6.(1)
Ifd2v=0,m34v=5, and ms4v≥1, then the remaining face is a 9+-face. Moreover, if d5v=4, then there is at least one 5-neighbor x of v on the 9+-face and m6+x≥2.(2)
Ifd2v=0 and m3v=5, then the remaining face is an 8+-face or a 4-face (as in case 1.1 of Figure 1). Moreover,(2.1) if the remaining face is an8+-face and any 3-neighbors and 5-neighbors are not adjacent, then m6+x≥2 for each 5-neighbor x of v(2.2) if the remaining face is a 4-face andδ1v≥4, then m7+x≥2 for each 4+- neighbor x of v(2.3) if the remaining face is a 4-face andδ1v=3, then there are two cases for each 6-neighbor x of v(2.3.1) ifx∈v1,v4,v6, then m3x≤3,m4x=1, and m7+x≥2(2.3.2) ifx∈v2,v3,v5, then m3x≤4 and m7+x≥2(3)
Ifd2v=1 and m3v=5, then the remaining face is an 8+-face other than cases 1.2–1.7 in Figure 1.(3.1)m3v2≤3 and m7+v2≥2 in Figure 1 (cases 1.2, 1.4, and 1.5)(3.2)m3v2≤3,m6+v2≥1, and m7+v2≥1 in Figure 1 (case 1.3)(3.3)m3v2≤3 and m8+v2≥1 in Figure 1 (cases 1.6 and 1.7)(4)
Ifd2v=0 and m34v=4, then m5+v=2, m7+v=1, or m4v=2(as in Figure 1, case 1.8). Furthermore, if m4v=2, then there are three cases for each 6-neighbor x of v(4.1) ifx∈v1,v4, then m3x≤2,m4x=2, and m8+x≥2(4.2) ifx∈v2,v5, then m3x≤4 and m8+x≥2(4.3) ifx∈v3,v6, then m3x≤3,m4x=1, and m8+x≥2(5)
Ifv is on a bad 4-face f=v1,v,v6,v2 satisfying dv1=2,m3v=4 and the remaining face is a 4-face or 5-face (as in Figure 1, cases 1.9–1.25), then there are four cases for vertex v2:(5.1)m3v2≤3,m4v2=1,m7+v2≥1, and m8+v2≥1 in Figure 1, cases 1.9–1.15(5.2)m3v2≤3,m4v2=1,m5v2=1, and m7+v2=1 in Figure 1, cases 1.16–1.21(5.3)m3v2≤2 and m4+v2=4 in Figure 1, cases 1.22–1.24(5.4)m3v2≤3,m4v2=2, and m8+v2=1 in Figure 1, case 1.25(6)
Ifm3v2=4,m4v2=1,m5v2=1, and v is on a 3-face f=v1,v,v2 satisfying dv1=2 and another face incident with v1 is a 5-face (as in Figure 1, cases 1.26–1.30), then there are three cases for vertex v2:(6.1)m3v2≤3,m4v2=1,m5v2=1, and m7+v2≥1 in Figure 1, case 1.26(6.2)m3v2≤2,m4v2=1,m5v2=1, and m7+v2≥1 in Figure 1, case 1.27(6.3)m3v2≤3,m5v2=1, and m7+v2≥2 in Figure 1, cases 1.28–1.30Figure 1
Black vertices do not have neighbors other than those presented in the picture; white vertices can be adjacent to some other vertices.Proof.
Letvi∈Nv,1≤i≤6 be arranged in a counterclockwise sequence. Let fi be the face incident with v, vi, and vi+1 (i∈1,2,…,6). Note that all the indices in this lemma are modulo 6 if it is larger than 6. Obviously, ms4v≤3 by Lemma 3.(1)
Ifms4v=3, then m3v=2 by Lemma 3. If ms4v=2, then m3v=3 by Lemma 3. Obviously, there are adjacent 8-cycles.Suppose thatms4v=1 and f1 is a bad 4-face. In that case, m3v=4,dv1=dv2=6, and d5+v=6. Three cases are discussed below from the perspective of symmetry. First, suppose that df2=df3=df4=df5=3. In the event of df6=i4≤i≤8, there are at least two adjacent 8-cycles in G. Thus, df6≥9. Moreover, if d5v=4, then v6 is on the 9+-face. Let f7,f8,f9 be the faces that are incident with v6 in an anticlockwise sequence. If df7=i,3≤i≤5, then there are at least two adjacent 8-cycles in G. Thus, df7≥6 and m6+v6≥2. Second, suppose that df2=df3=df4=df5=3. In the event of df5=i,4≤i≤8, there are at least two adjacent 8-cycles in G. Therefore, df5≥9. Moreover, if d5v=4, then v5 and v6 are on the 9+-face. Without loss of generality (WLOG), we consider the vertex v6. Let f7,f8,f9 be the faces that are incident with v6 in an anticlockwise sequence. In the event of df7=i,3≤i≤5, there are at least two adjacent 8-cycles in G. Hence, df7≥6 and m6+v6≥2. Third, suppose that df2=df3=df4=df5=3. In the event of df4=i,4≤i≤8, there are at least two adjacent 8-cycles in G. Therefore, df4≥9. Moreover, if d5v=4, then v4 and v5 are on the 9+-face. WLOG, we consider the vertex v5. Let f7,f8,f9 be the faces that are incident with v5 in an anticlockwise sequence. In the event of df7=i,3≤i≤5, there are at least two adjacent 8-cycles in G. Therefore, df7≥6 and m6+v5≥2.(2)
Suppose thatf1,f2,…,f5 are 3-faces. If df6=4, then there is only one case, as in Figure 1 (case 1.1). If df6=i,5≤i≤7, then there are at least two adjacent 8-cycles in G. Therefore, df6≥8.(2.1) Suppose that the remaining face is an8+-face and any 3-neighbors and any 5-neighbors of v are not adjacent. WLOG, we suppose that dv1=3, dvi=5,3≤i≤5, and v1 is not adjacent to vi,3≤i≤5. Let f7,f8,f9 be the faces that are incident with vi,3≤i≤5 in an anticlockwise sequence. If df7=i,3≤i≤5, then df8≥6 and df9≥6; otherwise, there are at least two adjacent 8-cycles in G. Thus, df7≥6. If df9=3, then df8≥6; otherwise, df9≥6. Thus, m6+vi≥2,3≤i≤5. If dv6=5 and v1 is not adjacent to v6, let f7,f8 be the faces that are incident with v6 in an anticlockwise sequence. If df7=i,3≤i≤5, then df6,df8≥6; otherwise, there are at least two adjacent 8-cycles in G. Thus, df7≥6 and m6+v6≥2. The proofs of cases dvi=3,2≤i≤6 are similar, so we only give the proof for dv1=3 here.(2.2) Suppose that the remaining face is a 4-face satisfyingδ1v≥4. Suppose that dv1≥4, another face incident with edge v1v4 is f7, and another face incident with edge v1v2 is f8. If df7=i,3≤i≤6, then there are at least two adjacent 8-cycles in G. Therefore, df7≥7. If df8=i,3≤i≤6, then there are at least two adjacent 8-cycles in G. Thus, df8≥7. The proofs of cases dvi=4,2≤i≤6 are similar, so we omit them here.(2.3) Suppose that the remaining face is a 4-face andδ1v=3.(2.3.1) Suppose thatdv1=6 and f7,f8,f9,f10 are the faces that are incident with v1 in an anticlockwise sequence. If df7=i,3≤i≤6, then there are at least two adjacent 8-cycles in G. Therefore, df7≥7. In the event of df10=3, df9≥7 (otherwise, there are at least two adjacent 8-cycles in G); otherwise, df10≥7. Thus, m3v1≤3,m4v1=1, and m7+v1≥2. The proofs of cases dv4=6 and dv6=6 are similar, so we omit them here.(2.3.2) Suppose thatdv2=6 and f7,f8,f9,f10 are the faces incident with v2 in an anticlockwise sequence. If df7=3 or df7=4, then df8≥7; otherwise, df7≥7 because no two adjacent 8-cycles appear in G. If df10=3 or df10=4, then df9≥7 because no two adjacent 8-cycles appear in G; otherwise df10≥7. The proofs of cases dv3=6 and dv5=6 are similar, so we omit them here.(3)
Suppose thatd2v=1,f3v=5, and f1,f2,…,f5 are 3-faces. In the event of df6=i,4≤i≤6, only three cases 1.2–1.7 in Figure 1 exist. If df6=7, then there are at least two adjacent 8-cycles in G. Thus, df6≥8. Let f7,f8,f9 be the faces that are incident with v2 in an anticlockwise sequence.(3.1) First, ifdf7=3, then df8≥7 and df9≥7. Second, if df7=i,4≤i≤6, then there are at least two adjacent 8-cycles in G. Therefore, df7≥7. If df9=3, then df8≥7; otherwise, there are at least two adjacent 8-cycles in G. If df9=i,4≤i≤6, then there are at least two adjacent 8-cycles in G. Thus, df9≥7. Therefore, m3v2≤3 and m7+v2≥2 in Figure 1 (case 1.2). Cases 1.4 and 1.5 in Figure 1 are similar, so we omit them here.(3.2) Ifdf7=i,3≤i≤5, then there are at least two adjacent 8-cycles in G. Thus, df7≥6. If df9=i,3≤i≤6, then there are at least two adjacent 8-cycles in G. Therefore, df9≥7. Hence, m3v2≤3,m6+v2≥1, and m7+v2≥1 in Figure 1, case 1.3.(3.3) Ifdf7=i,3≤i≤7, then there are at least two adjacent 8-cycles in G. Therefore, df7≥8. If df9=i,3≤i≤7, then there are at least two adjacent 8-cycles in G. Therefore, df9≥8. Hence, m3v2≤3 and m8+v2≥2 in Figure 1 (case 1.6). Case 1.7 in Figure 1 is similar, so we omit it here.(4)
Ifms4v=3, then f3v=1. WLOG, suppose that f1,f3,f5 are 3-faces and f2 is a bad 4-face. If df4=4, then there are at least two adjacent 8-cycles in G. Therefore, df4≥5 and df6≥5. Hence, m5+v=2.Ifms4v=2, then m3v=2. Two cases are discussed below from the perspective of symmetry. First, suppose that f1,f3 are bad 4-faces. If f2 and f4 are 3-faces, then df5≥5 and df6≥5; otherwise, there are at least two adjacent 8-cycles in G. If f2 and f5 are 3-faces, then df4≥5 and df6≥5; otherwise, there are at least two adjacent 8-cycles in G. If f4 and f6 are 3-faces, then df2≥5 and df5≥5; otherwise, there are at least two adjacent 8-cycles in G. If f4 and f5 are 3-faces, then df2≥5 and df6≥5; otherwise, there are at least two adjacent 8-cycles in G. Second, suppose that f1 and f4 are bad 4-faces. If f2 and f3 are 3-faces, then df5≥5 and df6≥5; otherwise, there are at least two adjacent 8-cycles in G. If f2 and f5 are 3-faces, then df3≥5 and df6≥5; otherwise, there are at least two adjacent 8-cycles in G. Thus, m5+v=2.Suppose thatms4v=1 and f1 is a bad 4-face. Then, f3v=3. Five cases are discussed below from the perspective of symmetry: f2,f3,f4, f3,f4,f5, f2,f3,f6, f2,f3,f5, or f2,f4,f6 is a 3-face. As the discussion of each case is similar, we only present the proof for the case in which f2,f3,f4 is a 3-face. If df5=4, then df6≥7; otherwise, df4≥5 and df6≥5. Thus, m5+v=2 or m7+v=1.Suppose thatd2v=0 and f4v=4. Three cases are discussed below from the perspective of symmetry. First, suppose that dfi=3,1≤i≤4. If df5=4, then df6≥7; if df5≥5, then df6≥5. Therefore, f5+v=2 or f7+v=1. Second, suppose that df1=df2=df3=df5=3. If df4=4, then df6≥7; if df4≥5, then df6≥5. Therefore, m5+v=2 or m7+v=1. Third, suppose that df1=df2=df4=df5=3. If df3=4, there are two cases: df6=4, as in case 1.8 of Figure 1, or df6≥7. If df3≥5, then df6≥5. Thus, m4v=2, m5+v=2, or m7+v=1.Suppose thatf4v=2. Symmetry means that there are three distinct cases: x∈v1,v4, x∈v2,v5, and x∈v3,v6. As the discussion of each case is similar, we only present a proof of x=v1 here. Let f7,f8,f9 be the faces that are incident with v1 in an anticlockwise sequence. If df7=i,3≤i≤7, then there are at least two adjacent 8-cycles in G. Thus, df7≥8. If df9=i,3≤i≤7, then there are at least two adjacent 8-cycles in G. Therefore, df9≥8. Hence, m3v1≤2,m4v1=2, and m8+v1≥2.(5)
Suppose thatv is on a bad 4-face f=v1,v,v6,v2 satisfying dv1=2,f3v=4. In this case, the remaining face is a 4-face or a 5-face, as in cases 1.9–1.25 in Figure 1. For vertex v2, there are four cases. As the discussion of each case is similar, we only present the proof for case 1.9 in Figure 1.Letf7,f8,f9 be the faces that are incident with v in an anticlockwise sequence. If df7=i,3≤i≤7, then there are at least two adjacent 8-cycles in G. Thus, df7≥8. If df9=i,3≤i≤6, then there are at least two adjacent 8-cycles in G. Thus, df9≥7. Hence, m3v2≤3,m4v2=1,m7+v2≥1, and m8+v2≥1 in case 1.9 of Figure 1.(6)
Suppose thatf3v=4,f4v=1,f5v=1, and v is on a 3-face f=v1,v,v2 satisfying dv1=2. In this case, another face that is incident with v1 is a 5-face (as in Figure 1, cases 1.26–1.30). For vertex v2, there are three cases. As the discussion of each case is similar, we only present the proof of case 1.26 in Figure 1.
Letf7,f8 be the faces that are incident with v in an anticlockwise sequence, besides the known faces. Face f7 cannot be a 3-face; otherwise, there would be a multiedge. If df7=i,4≤i≤6, then there are at least two adjacent 8-cycles in G. Therefore, df7≥7. Hence, m3v2≤3,m4v2=1,m5v2=1, and m7+v2≥1 in case 1.26 of Figure 1.Theorem 2.
Suppose thatG is a planar graph without any adjacent 8-cycles. If Δ≥6, then χ′G=Δ.Proof.
Suppose thatG is a counterexample to this theorem with the minimum number of edges and that G is embedded in the plane. Then, G is a 6-critical graph by Lemma 1, and it is 2-connected by Lemma 2. By Euler’s formula VG−EG+FG=2, we have that(1)∑x∈VGdx−4+∑x∈FGdx−4=−8<0.
Definech to be the initial charge and x∈V∪F. Suppose that chx=dx−4. Therefore, ∑x∈V∪Fchx<0. For x, we allocate a new charge ch′x in accordance with our discharging rules (see below). Because our rules only transfer charge between vertices and faces, they have no effect on the sum. In the event that ch′x≥0 for each x, we obtain an apparent contradiction: 0≤∑x∈V∪Fch′x=∑x∈V∪Fchx<0. This completes the proof.
The discharging rules are as follows:R1: letdf≥5 in G. Then, each vertex on f obtains df−4/df from f.R2: letdv=2 and m=mt+v,t≥5. If v is on a bad 4-face f=w,v,x,y such that w,v,x form a 3-face, then v obtains 1/3 from y and 5/6 from each neighbor. If v is on two 4-faces, then v obtains 1 from each neighbor. If v is on a 5+-face, then v obtains m⋅df−4/df from f, and at least 1−m/2+2m/df from each neighbor.R3: letdv=3. Each 3-vertex obtains 1/3 from each neighbor.R4: letdv=4 and m=mt+vt≥5. If vx∈EG,dx=6, and x satisfies (1) m3x=6, (2) m3x=5 and d2x=0, or (3) d2x=0,m3x=4, and m4x=2, then v sends m⋅df−4/df to x.R5: letf be a 3-face x,y,z satisfying dx≤dy≤dz. If 2≤dx≤4 and mindy,dz≥5, then f obtains 1/2 from y and 1/2 from z. If dx=dy=4 and dz=6, then f obtains 1 from z. If mindx,dy,dz≥5, then f obtains 1/3 from each of x,y,z.R6: letdv=5.R6.1: suppose thatvx∈EG and dx=6. If m6+v≥2, then v obtains 0 from x. Otherwise, if v is on a 3,5,6-face u,v,w satisfying ux∉EG and w≠x, then v obtains 2/3 from x. Otherwise, v obtains 1/4 from x.R6.2: ifm3v=5, vx∈EG, and dx=5, then m3x≤3, and m6+x≥2 or m8+x≥1. If m6+x≥2, then v obtains 1/3 from x; if m8+x≥1, then v obtains 1/2 from x.R7: letdv=6.R7.1: suppose thatm3v=6 and v is on a 3-face f=u,v,w satisfying du=3 and dw=6. Then, v obtains 2/3 from w.R7.2: suppose thatd2v=1,m3v=5, and v is incident with a 3-face f=u,v,w such that du=2. If another face that is incident with u is an i-face (i∈4,5,6) (i.e., cases 1.2–1.7 in Figure 1), then v obtains 5/6 from w. If another face that is incident with u is an 8+-face, then v obtains 1/12 from w.R7.3: suppose thatd2v=0,m3v=5,m4v=1, and δ1v=3. If w is a 6-neighbor of v, then m7+w≥2 by Lemma 5 (2.3) and v obtains 1/3 from w.R7.4: suppose thatd2v=0,m3v=4, and m4v=2 (i.e., case 1.1 in Figure 1). If w is a 6-neighbor of v, then m8+w≥2 by Lemma 7 (4) and v obtains 1/3 from w.R7.5: ifv is on a bad 4-face f=u,v,z,w satisfying du=2,m3v=4, and m6+v=0 (i.e., cases 1.9–1.25 in Figure 1), then v obtains 1/3 from w.R7.6: ifm3v=4,m4v=1,m5v=1, and v is on a 3-face f=u,v,w satisfying du=2 and another face that is incident with u is a 5-face (i.e., cases 1.26–1.30 in Figure 1), then v obtains 1/5 from w.
In the following, we start to verifych′x≥0 for all x∈V∪F. Suppose that f∈FG, and obviously, df≥3. In the event of df≥5, ch′f≥1−df−4/t×t=0 by R1. In the event of df=4, ch′f=0. Suppose that df=3. As Δ=6, f must be a 2+,6,6-face, 3,5+,6-face, 4,4,6-face, or 4+,5+,5+-face by Lemma 2. Therefore, ch′f=−1+min2×1/2,1,3×1/3=0 by R5.
Letw∈VG. Obviously, dw≥2. In the event of dw=2, w has two 6-neighbors by Lemma 2. Therefore, ch′w=−2+min1/3+2×5/6,2×1,t⋅df−4/df+2×1−t/2+2t/df=0 by R2. In the event of dw=3, d5+w≥3 by Lemma 2. Therefore, ch′w=−1+3×1/3=0 by R3. In the event of dw=4, ch′w=m⋅df−4/df−m⋅df−4/df=0 or ch′w=chw=0 by R1 and R4.
There are only two cases left to test.Case 1.
Suppose thatdw=5. By Lemma 2, d3w≤1 and d6w≥2.
Suppose thatδ1w=6. If m3w≤3, then ch′w≥1−3×1/3=0 by R5 and R6.1; otherwise, m3w≥4, and then ch′w≥1+5×1/4−5×1/3=7/12>0 by R5 and R6.1.
Suppose thatδ1w=5 (denote one 5-neighbor of w as w0). Then, d6w≥2 by Lemma 2. There are three situations. First, suppose that m3w≤3. If m3w0=5, then m6+w≥2 or m8+w≥1 because there are no two adjacent 8-cycles in G. By R6.2, w sends 1/3 or 1/2 to w0. If m6+w≥2, then ch′w≥1+2×1/3−1/3−3×1/3=1/3>0 by R1, R5, and R6.1. If m8+w≥1, then ch′w≥1+1/2+2×1/4−3×1/3−1/2=1/2>0 by R1, R5, and R6.1. Otherwise, m3w0≤4, and w sends no charge to w0. Then, ch′w≥1+min2×1/4,2×1/3,1/2−3×1/3=1/2>0 by R5 and R6. Second, if m3w=4, then ch′w≥1+2×1/4−4×1/3=1/6>0 by R5 and R6.1. Third, suppose that m3w=5. If d6w≥3, then ch′w≥1+3×1/4−5×1/3=1/12>0 by R5 and R6.1; otherwise, d6w=2, and then m6+w0≥2 or m8+w≥1 because there are no two adjacent 8-cycles in G. Therefore, w0 sends 1/3 or 1/2 to w by R6.2 and ch′w≥1+2×1/4+1/3−5×1/3=1/6>0 or ch′w≥1+2×1/4+1/2−5×1/3=1/3>0 by R5 and R6.1.
Suppose thatδ1w=4. By Lemma 2, d6w≥3, and, by Lemma 4, w is on at most two 4,5,5+-faces. There are several subcases. First, d6w=3 and d4w=2. Thus, m3w≤4. If m3w≤3, then ch′w≥1+min3×1/4,2×1/3−2×1/2−1/3=1/3>0 by R5 and R6.1; otherwise, m3w=4, and then ch′w≥1+3×1/4−2×1/2−2×1/3=1/12>0 by R5 and R6.1. Second, d6w=3 and d5w=1 (mark the 5-vertex as w0). If m3w0=5, then m3w≤3, and m6+w≥2 or m8+w≥1 because no two adjacent 8-cycles appear in G. By R6.2, w sends 1/3 or 1/2 to w0. If m6+w≥2, then ch′w≥1+2×1/3−1/3−2×1/2−1/3=0 by R1, R5, and R6.1. If m8+w≥1, then ch′w≥1+1/2+2×1/4−1/3−2×1/2−1/3=1/3>0 by R1, R5, and R6.1. Otherwise, m3w0≤4, and w sends no charge to w0. If m3w≤4, then ch′w≥1+min3×1/4,2×1/3−2×1/2−2×1/3=0 by R5 and R6.1. If m3w=5, then m6+w0≥2 or m8+w≥1 because G contains no adjacent 8-cycles. Thus, w0 sends 1/3 or 1/2 to w by R6.2, and ch′w≥1+3×1/4+1/3−2×1/2−3×1/3=1/12>0 or ch′w≥1+3×1/4+1/2−2×1/2−3×1/3=1/4>0 by R5 and R6.1. Third, d6w=4. Suppose that m3w≤4. If m6+w≥2, then ch′w≥1+2×1/3−3×1/3=2/3>0 by R5 and R6.1; otherwise, m6+w≤1, and then ch′w≥1+4×1/4−2×1/2−2×1/3=1/3>0 by R5 and R6.1. If m3w=5, then ch′w≥1+4×1/4−2×1/2−3×1/3=0 by R5 and R6.1.
Suppose thatδ1w=3 (mark the 3-vertex as w0). Then, d6w=4 by Lemma 2. Suppose that m3w0=0. If m6+w≥2, then ch′w≥1+2×1/3−1/3−3×1/3=1/3>0 by R3, R5, and R6.1; otherwise, m6+w≤1, and then ch′w≥1+4×1/4−1/3−3×1/3=2/3>0 by R3, R5, and R6.1. If m3w0≥1, then ch′w≥1+2×2/3−1/3−2×1/2−3×1/3=0 by R5 and R6.1.Case 2.
Letdw=6. By Lemma 2, m3w≤6, d2w≤1, and d6w≥2.
In the process of discharging, there are some special cases. That is, some 6-vertices discharge to other 6-vertices. Therefore, we now individually verify these special cases. In the following, we need to check the two following subcases.Subcase 1.
w gives some charge to some 6-vertex v (see R7).
Suppose thatw is on a 3-face f=u,v,w satisfying du=3 and m3v=6. If m3u=3, then m3w≤4,m7+w≥1, and m8+w≥1 because no two adjacent 8-cycles appear in G. As du=3, we have that d6w≥4 by Lemma 2, δ1w=3 by Lemma 3, and δ2w≥5 by Lemma 4. Thus, ch′w≥2+1/2+3/7−2×1/2−2×1/3−1/3−2/3−1/4=1/84>0 by R1, R3, R5, R6.1, and R7.1. Otherwise, m4+u=1, and then m8+w≥2 and m3w≤4. Because δ1w=3, we have that d6w≥4 by Lemma 2 and δ2w≥4 by Lemma 4. Therefore, ch′w≥2+2×1/2−2×1/2−2×1/3−1/4−2/3=5/12>0 by R1, R3, R5, R6.1, and R7.1.
Suppose thatw is on a 3-face f=u,v,w satisfying du=2,m3v=5. If a 4-face is incident with u, then m3w≤3 and m7+w≥2 by Lemma 7 (3). By R1, R2, R5, and R7.2, ch′w≥2+2×3/7−5/6−1/2−2×1/3−5/6=1/42>0. If a 5-face is incident with u, then there are two cases: (1) m3w≤3,m6+w≥1, and m7+w≥1. In this case, ch′w≥2+1/5+1/3+3/7−5/6−1/2−2×1/3−5/6=9/70>0 by R1, R2, R5, and R7.2. (2) m3w≤3 and m7+w≥2. By R1, R2, R5, and R7.2, ch′w≥2+1/5+2×3/7−5/6−1/2−2×1/3−5/6=47/210>0. If a 6-face is incident with u, then there are two cases: (1) m3w≤3 and m7+w≥2. In this case, ch′w≥2+1/3+2×3/7−5/6−1/2−2×1/3−5/6=5/14>0 by R1, R2, R5, and R7.2. (2) m3w≤3 and m8+w≥1. In this case, ch′w≥2+1/3+1/2−5/6−1/2−2×1/3−5/6=0 by R1, R2, R5, and R7.2. If an 8+-face is incident with u, then m3w≤4,m7+w≥1, and m8+w≥1 because no two adjacent 8-cycles appear in G. Therefore, ch′w≥2+1/2+3/7−3/4−1/2−3×1/3−1/12=43/84>0 by R1, R2, R5, and R7.2.
Suppose thatwv∈EG and dv=6 such that d2v=0,m3v=5,m4v=1, and δ1v=3 (i.e., case 1.1 in Figure 1). Because δ1v=3, we know that δ1w≥3 by Lemma 3. First, if w∈v1,v4,v6, then m3w≤3,m4w=1, and m7+w≥2. By R7.3, w sends 1/3 to v. If δ1w=3, ch′w≥2+2×3/7−2×1/2−1/3−2×1/3−1/3=11/21>0 by R1, R2, and R5. If δ1w=4, ch′w≥2+2×3/7−max1+2×1/2,3×1/2+2×1/4−1/3=11/21>0 by R1, R2, and R5. If δ1w≥5, ch′w≥2+2×3/7−3×1/3−max2/3,2×1/4,3×1/4,4×1/4−1/3=11/21>0 by R1, R2, and R5. Second, if w∈v2,v3,v5, then m3w≤4 and m7+w≥2. By R7.3, w sends 1/3 to v. If δ1w=3, then ch′w≥2+2×3/7−max1/2+3×1/3+2×1/3,1/2+3×1/3+1/3+1/4,2×1/2+2×1/3+1/3+1/4−1/3=23/84>0 by R1, R2, and R5. Assume that δ1w=4. If w is not on any 4,4,6-face, then, by R1, R2, and R5, ch′w≥2+2×3/7−4×1/2−1/4−1/3=23/84>0. Therefore, w is on a 4,4,6-face, and ch′w≥2+2×3/7−1−2×1/2−1/3−1/3=4/21>0 by R1, R2, and R5. If δ1w≥5, ch′w≥2+2×3/7−4×1/3−max2/3,2×1/4,3×1/4,4×1/4−1/3=4/21>0 by R1, R2, and R5.
Suppose thatwv∈EG and dv=6 such that d2v=0,m3v=4,m4v=2 (i.e., case 1.8 in Figure 1). First, if w∈v1,v4, then m3w≤2,m4w=2, and m8+w≥2. By R7.4, w sends 1/3 to v. If δ1w=2, then ch′w≥2+2×1/2−1−1/2−1/3−1/3=5/6>0 by R1, R2, and R5. If δ1w=3, then ch′w≥2+2×1/2−2×1/2−2×1/3−1/3=1>0 by R1, R2, and R5. If δ1w=4, then ch′w≥2+2×1/2−max1+1/2,2×1/2+2×1/4−1/3=7/6>0 by R1, R2, and R5. If δ1w≥5, then ch′w≥2+2×1/2−2×1/3−max2/3,2×1/4,3×1/4,4×1/4−1/3=1>0 by R1, R2, and R5. Second, if w∈v2,v5, then m3w≤4 and m8+w≥2. By R7.4, w sends 1/3 to v. If δ1w=2, then ch′w≥2+2×1/2−1−1/2−3×1/3−1/3=1/6>0 by R1, R2, and R5. If δ1w=3, then ch′w≥2+2×1/2−max4×1/2+2×1/3,4×1/2+1/3,2×1/2+2×1/3+1/3+1/4−1/3=0 by R1, R2, and R5. Assume that δ1w=4. If w is not on any 4,4,6-face, then ch′w≥2+2×1/2−4×1/2−1/3−1/4=5/12>0 by R1, R2, and R5. Thus, w is on a 4,4,6-face. By R1, R2, and R5, ch′w≥2+2×1/2−1−2×1/2−1/3−1/3=1/3>0. If δ1w≥5, then ch′w≥2+2×1/2−4×1/3−max2/3,2×1/4,3×1/4,4×1/4−1/3=1/3>0 by R1, R2, and R5. Third, if w∈v3,v6, then m3w≤3,m4w=1 and m8+w≥2. By R7.4, w sends 1/3 to v. If δ1w=2, then ch′w≥2+2×1/2−1−1/2−2×1/3−1/3=1/2>0 by R1, R2, and R5. If δ1w=3, then ch′w≥2+2×1/2−max3×1/2+2×1/3,3×1/2+1/3,2×1/2+1/3+1/3+1/4−1/3=1/2>0 by R1, R2, and R5. If δ1w=4, then ch′w≥2+2×1/2−max1+2×1/2,3×1/2+1/4−1/3=2/3>0 by R1, R2, and R5. If δ1w≥5, then ch′w≥2+2×1/2−3×1/3−max2/3,2×1/4,3×1/4,4×1/4−1/3=2/3>0 by R1, R2, and R5.
Suppose thatw is on a bad 4-face f=u,v,w satisfying du=2 with v satisfying d2v=1, m3v=4. By Lemma 7 (5), there are four cases: (1) m3w≤3,m4w=1 and m7+w≥1,m8+w≥1. Then, ch′w≥2+1/2+3/7−5/6−1/2−2×1/3−1/3=25/42>0 by R1, R2, R5, and R7.5. (2) m3w≤3,m4w=1, and m5w=1,m7+w≥1. Then, ch′w≥2+1/5+3/7−5/6−1/2−1/3−1/3=31/105>0 by R1, R2, R5, and R7.5. (3) m3w≤2 and m4+w≥2. Then, ch′w≥2−5/6−1/2−1/3−1/3=0 by R1, R2, R5, and R7.5. (4) m3w≤3,m4w=2 and m8+w≥2. Then,ch′w≥2+1/2−5/6−1/2−2×1/3−1/3=1/6>0 by R1, R2, R5, and R7.5.
Suppose thatw is on a 3-face f=u,v,w satisfying du=2 and another face incident with u is a 5-face, with v satisfying m3v=4,m4v=1,m5v=1. By Lemma 7 (6), there are three cases: (1) m3w≤3,m4w=1,m5w=1, and m7+w≥1. Therefore, ch′w≥2+1/5+3/7−9/10−1/2−2×1/3−1/5=31/105>0 by R1, R2, R5, and R7.6. (2) m3w≤2,m4w=1,m5w=1, and m7+w≥1. Then, ch′w≥2+1/5+3/7−9/10−1/2−1/3−1/5>0 by R1, R2, R5, and R7.6. (3) m3w≤3,m5w=1, and m7+w≥2. Then, ch′w≥2+2×3/7−9/10−1/2−2×1/3−1/5>0 by R1, R2, R5, and R7.6.Subcase 2.
w gives no charge to other 6-vertices.
Letw1,w2,…,w6 be neighbors of w in an anticlockwise order and let f1,f2,…,f6 be the faces that are incident with w such that fi is incident with wi and wi+1 for all i∈1,2,…,6, where w7=w1.Subcase 3.
m34w≤3.
In the event ofδ1w≥5, d6w≥2 by Lemma 2. Therefore, ch′w≥2−3×1/3−max2/3,2×1/4,3×1/4,4×1/4=0 by R5 and R6.1.
Suppose thatδ1w=4. By Lemma 2, d6w≥3. Suppose that w is not on any 4,4,6-face. In the event of d5w≤1, ch′w≥2−3×1/2−1/4=1/4>0 by R5 and R6.1; otherwise, d5w=2, and so ch′w≥2−2×1/2−1/3−2×1/4=1/6>0 by R5 and R6.1. In light of this, w is on a 4,4,6-face, and so ch′w≥2−2×1/2−1=0 by R5.
Suppose thatδ1w=3 (mark this vertex as x). By Lemma 2, d6w≥4. If δ2w=3 (mark this vertex as y), then wx and wy are not on any 3-face by Lemma 4. Thus, ch′w≥2−3×1/3−2×1/3>0 by R2 and R3. In the event of δ2w=4 (mark this vertex as y), wx is on at most one 3-face and wy is not on any 3-face by Lemma 4. Therefore, ch′w≥2−1/2−2×1/3−1/3>0 by R3 and R5. If δ2w=5 (mark this vertex as y), then w gives at most 1/4 to y by R6.1. Hence, ch′w≥2−2×1/2−2×1/3−1/4=1/12>0 by R3 and R5.
Suppose thatδ1w=2 (mark this vertex as u). By Lemma 3, d6w=5 and ms4w=0. In the event of m3w≤2, ch′w≥2−1−1/2−1/3=1/6>0 by R2 and R5; otherwise, m3w=3. If u is on a bad 4-face, then ch′w≥2−5/6−1/2−2×1/3=0 by R2 and R5. If u is on a 3-face and a 5+-face, then ch′w≥2+1/5−1−1/2−2×1/3=1/30>0 by R1, R2, and R5. If v is on two 4+-faces, then ch′w≥2−1−3×1/3=0 by R2 and R5.Subcase 4.
m34w=4.Subcase 5.
d2w=0.
By Lemma 7 (4),m5+w=2, m7+w=1, or m4w=2.Subcase 6.
m5+w=2 or m7+w=1.
Suppose thatδ1w≥5, so that d6w≥2 by Lemma 2. Thus, ch′w≥2+2×1/5−4×1/3−max2/3,2×1/4,3×1/4,4×1/4=1/15>0 or ch′w≥2+3/7−4×1/3−max2/3,2×1/4,3×1/4,4×1/4=2/21>0 by R1, R5, and R6.1.
Suppose thatδ1w=4. Then, d6w≥3 by Lemma 2. Suppose that w is not on any 4,4,6-face. If d5w≤1, then ch′w≥2+2×1/5−4×1/2−1/4=3/20>0 or ch′w≥2+3/7−4×1/2−1/4=5/28>0 by R1, R5, and R6.1; otherwise, d5w=2, and so ch′w≥2+2×1/5−2×1/2−2×1/3−2×1/4=7/30>0 or ch′w≥2+3/7−2×1/2−2×1/3−2×1/4=11/42>0 by R1, R5, and R6.1. Therefore, w is on one 4,4,6-face. Then, ch′w≥2+2×1/5−1−2×1/2−1/3=1/15>0 or ch′w≥2+3/7−1−2×1/2−1/3=2/21>0 by R1, R5, and R6.1.
Suppose thatδ1w=3 (mark this vertex as x). Then, d6w≥4 by Lemma 2 and ms4w=0 by Lemma 5. If δ2w=3 (mark this vertex as y), then wx and wy are not on any 3-face by Lemma 4 and m3w≤3. This is impossible. If δ2w=4 (mark this vertex as y), then wx is on at most one 3-face and wy is not on any 3-face by Lemma 4. Therefore, ch′w≥2−1/2−3×1/3−1/3=1/6>0 by R3 and R5. If δ2w=5 (mark this vertex as y), then w gives at most 1/4 to y by R6.1. Then, ch′w≥2+2×1/5−2×1/2−2×1/3−1/3−1/4=3/20>0 or ch′w≥2+3/7−2×1/2−2×1/3−1/3−1/4=5/28>0 by R1, R3, R5, and R6.1.Subcase 7.
m4w=2.
In the event ofδ1w=6, ch′w≥2−4×1/3>0 by R5.
Suppose thatδ1w=5. By Lemma 2, d6w≥2. Then, ch′w≥2+1/3−4×1/3−max2/3,2×1/4,3×1/4,4×1/4=0 by R5, R6.1, R6.3, and R7.4.
Suppose thatδ1w=4. Then, d6w≥3 by Lemma 2. Suppose that w is not on any 4,4,6-face. If d5w≤1, then ch′w≥2+1/3−4×1/2−1/4=1/12>0. If d5w=2, then ch′w≥2+1/3−2×1/2−2×1/3−1/4=1/6>0 by R5, R6.1, R6.3, and R7.4. Therefore, w is on one 4,4,6-face. Then, ch′w≥2+1/3−1−1/2−2×1/3=1/6>0 by R5, R6.1, R6.3, and R7.4.
Suppose thatδ1w=3. At this point, d6w≥4 by Lemma 2 and δ2w≥5 by Lemma 4. Thus, ch′w≥2+1/3−2×1/2−2×1/3−1/3−1/4=1/12>0 by R5, R6.1, R6.3, and R7.4.Subcase 8.
d2w=1.
Marku as the 2-neighbor of w and let v be another neighbor of u. There are five scenarios to discuss: (1) If u is on a 3-face and an 8+-face, then the 8+-face gives at least 1/2 to w by R1. Therefore, ch′w≥2+1/2−3/4−1/2−3×1/3=1/4>0 by R2 and R5. (2) If u is on a 3-face and a 7-face, then ch′w≥2+3/7−11/14−1/2−3×1/3=1/7>0 by R1, R2, and R5. (3) If u is on one 3-face and one 6-face, then ch′w≥2+1/3−5/6−1/2−3×1/3=0 by R1, R2, and R5. (4) If u is incident with one 3-face and one 5-face, then the remaining face of w is a 5+-face or a 4-face. If the remaining face of w is a 5+-face, then ch′w≥2+2×1/5−9/10−1/2−3×1/3=0 by R1, R2, and R5; otherwise, the remaining face of w is a 4-face, and then v gives 1/5 to w by R7.6, so ch′w≥2+1/5+1/5−9/10−1/2−3×1/3=0 by R1, R2, and R5. (5) w is on a bad 4-face f=v,u,w,z satisfying wv∈EG. If the remaining face of w is a 4-face or a 5-face, then v gives 1/3 to w by R7.5, so ch′w≥2+1/3−5/6−1/2−3×1/3=0 by R1, R2, and R5. If the remaining face of w is a 6+-face, then ch′w≥2+1/3−5/6−1/2−3×1/3=0 by R1, R2, and R5.Subcase 9.
m34w=5.Subcase 10.
ms4w≥1.
By the proof of Lemma 7 (1), we know thatms4w=1 and m3w=4. By Lemmas 7 (1) and Lemma 3, the remaining face is a 9+-face and the neighbors of w are 5+-vertices. If δ1w=6, then ch′w≥2+5/9−5×1/3>0 by R1 and R5. Suppose that δ1w=5. By Lemma 2, d6w≥2. If d5w≤3, then ch′w≥2+5/9−5×1/3−max2/3,2×1/4,3×1/4=5/36>0 by R1, R5, and R6.1; otherwise, d5w=4. Then, there is at least one 5-vertex on the 9+-face, and this 5-vertex is on another 6+-face by Lemma 7 (1). Hence, by R6.1, w sends no charge to the 5-vertex and ch′w≥2+5/9−5×1/3−max2/3,2×1/4,3×1/4=5/36>0 by R1 and R5.Subcase 11.
m3w=5.
WLOG, we assume thatf1,f2,…,f5 are 3-faces. In the following, we need to consider two situations.Subcase 12.
d2w=0.
The remaining face is an8+-face or a 4-face by Lemma 7 (2).Subcase 13.
The remaining face is an8+-face.
Ifδ1w=6, then ch′w≥2+1/2−5×1/3>0 by R1 and R5.
Suppose thatδ1w=5. By Lemma 2, d6w≥2. By Lemma 7 (2.1), each 5-neighbor of w is on at least two 6+-faces. Thus, by R6.1, w sends no charge to the 5-neighbor and ch′w≥2+1/2−5×1/3>0.
Suppose thatδ1w=4. Then, d6w≥3 by Lemma 2. Suppose that w is not on any 4,4,6-face. If d5w=0, then ch′w≥2+1/2−5×1/2=0 by R1 and R5; otherwise, d5w≥1. If dw1=5, then m6+w1≥2 by Lemma 7 (2.1). Therefore, ch′w≥2+1/2−4×1/2−1/3=1/6>0 by R1, R5, and R6.1. The cases dwi=5,2≤i≤6 are the same as dw1=5, so we omit them. Therefore, w is on one 4,4,6-face. If f1 or f5 is a 4,4,6-face, then ch′w≥2+1/2−1−1/2−3×1/3=0 by R1 and R5. If f2 is a 4,4,6-face, then m5+w2≥1 or m5+w3≥1 because no two adjacent 8-cycles appear in G. By R4, w2 or w3 sends at least 1/5 to w. Thus, ch′w≥2+1/2+1/5−1−2×1/2−2×1/3=1/30>0 by R1 and R5. If f4 is a 4,4,6-face, it is similar to f2. If f3 is a 4,4,6-face, then f5+w3≥1 or m5+w4≥1 because no two adjacent 8-cycles appear in G. By R4, w3 or w4 sends at least 1/5 to w. Hence, ch′w≥2+1/2+1/5−1−2×1/2−2×1/3=1/30>0 by R1 and R5.
Suppose thatδ1w=3. Therefore, δ2w≥5 by Lemma 4 and d6w≥4 by Lemma 2. In the event of δ2w=6, we find that ch′w≥2+1/2−2×1/2−3×1/3−1/3=1/6>0 by R1, R3, and R5. Suppose that δ2w=5. If the 3-neighbor of w is adjacent to a 5-neighbor, then w sends no charge to the 5-neighbor by R6.1 and ch′w≥2+1/2−1−2×1/2−2×1/3−1/3=1/6>0 by R1, R3, and R5. Thus, the 3-neighbor of w is not adjacent to the 5-neighbor. WLOG, we assume that dw2=3, and so dw4=5, dw5=5, or dw6=5. Now, we can assume that dw4=5, in which case m6+w4≥2 by Lemma 7 (2.1). Thus, ch′w≥2+1/2−2×1/2−3×1/3−1/3=1/6>0 by R1, R3, and R5. If dwi=3 (i∈1,3,4,5,6), then this is similar to the case dw2=3, and so we omit it here.Subcase 14.
The remaining face is a 4-face.
Ifδ1w=6, then ch′w≥2−5×1/3>0 by R5.
Suppose thatδ1w=5. Then, d6w≥2 by Lemma 2 and every 5-neighbor of w is on at least two 7+-faces by Lemma 7 (2.2). Therefore, w sends no charge to its 5-neighbors and ch′w≥2−5×1/3>0 by R5.
Suppose thatδ1w=4. Then, d6w≥3 by Lemma 2 and every 4-neighbor of w is on at least two 7+-faces by Lemma 7 (2.2). Thus, the 4-neighbor gives at least 2×3/7 to w by R4 and ch′w≥2+2×3/7−max5×1/2,4×1/2+1/3,1+1/2+3×1/3,1+2×1/2+2×1/3=4/21>0 by R5.
Suppose thatδ1w=3. Then, δ2w≥5 by Lemma 4 and d6w≥4 by Lemma 2. Each 6-neighbor sends 1/3 to w by R7.3. Thus, ch′w≥2+2×1/3−max2×1/2+3×1/3+1/3,1/2+4×1/3+1/3−1/4=1/12>0 by R5.Subcase 15.
d2w=1.
The remaining face is an8+-face or cases 1.2–1.7 in Figure 1.
If the remaining face is a 4-face, thenw2 sends 5/6 to w by R7.2. Thus, ch′w≥2+5/6−1−1/2−4×1/3=1/42>0 by R2 and R5. If the remaining face is a 5-face, then w2 sends 5/6 to w by R7.2. Then, ch′w≥2+5/6−9/10−1/2−4×1/3=1/10>0 by R2 and R5. If the remaining face is a 6-face, then w2 sends 5/6 to w by R7.2. Thus, ch′w≥2+5/6−5/6−1/2−4×1/3=1/6>0 by R2 and R5. If the remaining face is an 8+-face, then w2 sends 1/12 to w by R7.2. Then, ch′w≥2+1/2+1/12−3/4−1/2−4×1/3=0 by R2 and R5.Subcase 16.
m3w=6.
Obviously,δ1w≥3. If δ1w=6, then ch′w≥2−6×1/3=0 by R5.
Suppose thatδ1w=5. Then, d6w≥2 by Lemma 2. WLOG, we suppose that dw1=5 and the other three faces of w1 are denoted as f7,f8,f9 in anticlockwise order. As no two adjacent 8-cycles appear in G, we have that df7≥6,df9≥6, and w sends no charge to its 5-neighbors by R6.1. Thus, ch′w≥2−6×1/3=0 by R5.
Suppose thatδ1w=4. Then, d6w≥3 by Lemma 2. Suppose that w is not on any 4,4,6-face. WLOG, we suppose that dw1=4 and the other two faces of w1 are denoted as f7,f8 in anticlockwise order. As no two adjacent 8-cycles appear in G, we have that df7≥6,df8≥6, and w1 sends 2/3 to w by R4. If w is adjacent to a 5-neighbor, then the 5-neighbor is incident with at least two 6+-faces because no two adjacent 8-cycles appear in G. Thus, w sends no charge to its 5-neighbors. If d4w=1, then ch′w≥2+2/3−2×1/2−4×1/3=1/3>0 by R5. If d4w=2, then ch′w≥2+2×2/3−4×1/2−2×1/3=1/3>0 by R5. If d4w=3, then ch′w≥2+3×2/3−6×1/2=1>0 by R5. Thus, w is incident with one 4,4,6-face. WLOG, we suppose that f1 is a 4,4,6-face and that w1 and w2 are on two 6+-faces because no two adjacent 8-cycles appear in G. Thus, w1 and w2 send at least 2/3 to w by R4. Therefore, ch′w≥2+2×2/3−1−2×1/2−3×1/3=1/3>0 by R5.
Suppose thatδ1w=3. Therefore, δ2w≥5 by Lemma 4 and d6w≥4 by Lemma 2. There are two subcases. First, we suppose that δ2w=6 and dw1=3 (WLOG), and then dwi=6,2≤i≤6. By R7.1, w2 and w6 each send 2/3 to w. Thus, ch′w≥2+2×2/3−2×1/2−4×1/3−1/3=2/3>0 by R3 and R5. Second, we suppose that δ2w=5. (1) Suppose that the 3-neighbor of w is adjacent to a 5-neighbor. WLOG, we suppose that dw1=3 and dw2=5. Then, w6 sends 2/3 to w by R7.1. Thus, ch′w≥2+2/3−2×1/2−4×1/3−1/3=0 by R5. (2) Suppose that the 3-neighbor of w is not adjacent to a 5-neighbor. WLOG, we assume that dw1=3, and then dw2=6 and dw6=6. Now, dw3=5, dw4=5, or dw5=5. Obviously, the 5-neighbor is on at least two 6+-faces because G contains no adjacent 8-cycles. Thus, w sends no charge to the 5-neighbor. By R7.1, w2 and w6 each send 2/3 to w. Thus, ch′w≥2+2×2/3−2×1/2−4×1/3−1/3=2/3>0 by R5.



---

*Source: 3562513-2021-06-01.xml*