Planar graphs without 4- and 6-cycles are (7 : 2)-colorable

Abstract

Let $G=(V(G),E(G))$ be a graph and s, t integers with $s\le t$. If we can assign an s-subset $\phi (v)$ of the set $\{1, 2,\ldots ,t\}$ to each vertex v of V(G) such that $\phi (u)\cap \phi (v)=\emptyset$ for every edge $uv\in E(G)$, then G is called (t : s)-colorable, and such an assignment $\phi$ is called a (t : s)-coloring of G. Let $C_n$ denote a cycle of length n. In this paper, we show that every planar graph without $C_4$ and $C_6$ is (7 : 2)-colorable and thus has fractional chromatic number at most 7/2.

1 Introduction

Let $G=(V(G),E(G))$ be a simple graph and s, t be integers with $s\le t$. A (t : s)-coloring of a graph G is a mapping $\phi$ from V(G) to s-subsets of $\{1,2,\ldots ,t\}$ such that $\phi (u)\cap \phi (v)=\emptyset$ if $uv\in E(G)$, and G is called (t : s)-colorable if it has a (t : s)-coloring. The minimum fraction t/s for which G is (t : s)-colorable is called the fractional chromatic number of G, and denoted by $\chi _f(G)$. Note that a (k : 1)-coloring is exactly an ordinary proper k-coloring. Then $\chi _f(G)\le \chi (G)$ for any graph G, where $\chi (G)$ is the chromatic number of G. The parameter $\chi _f(G)$ of a graph G was introduced by Hilton et al. (1973, 1975), and studied by Bollobás and Thomason (1979), Scott (1975), Stahl (1976) and some others. In 2011, Scheinerman and Ullman (2011) succinctly described the state of the art for fractionally coloring graph.

Steinberg conjectured Borodin et al. (2005) that every planar graph without 4- and 5-cycles is 3-colorable. Though this conjecture was disproved by Cohen-Addad et al. (2017) recently, Dvořák and Hu (2019) were able to show that every planar graph without 4- and 5-cycles is (11 : 3)-colorable. Before this, Steinberg (1993) suggested the following relaxation of Steinberg conjecture: Determine the smallest value of k, if it exists, such that every planar graph without cycles of length from 4 to k is 3-colorable. The best known bound for such k is 7, due to Borodin et al. (2005), and the result of Cohen-Addad et al. (2017) showed that the smallest value of k is at least 6. However, it remains open whether a planar graph without cycles of length from 4 to 6 is 3-colorable. If the answer to the problem is “YES”, then we have $\chi _f \le \chi \le 3$, that is, every planar graph without cycles of length from 4 to 6 is (6 : 2)-colorable. Up to now, no reports show that such planar graphs are (6 : 2)-colorable. On the other hand, since the upper bound of $\chi _f$ equals to 4 for any planar graph, that is, every planar graph is (8 : 2)-colorable, one may ask that whether every planar graph without cycles of length from 4 to 6 is (7 : 2)-colorable? In the paper, we answer the problem in positive.

Theorem 1.1

Every planar graph without $C_4$ and $C_6$ is (7 : 2)-colorable.

Obviously, Theorem 1.1 gives a positive support to the problem whether every planar graph without cycles of length from 4 to 6 is 3-colorable.

The independence number $\alpha (G)$ of a graph G is the size of a largest independent set in G. Since $\alpha (G)\ge \frac{|V(G)|}{\chi _f(G)}$ for any graph G, we have the following corollary by Theorem 1.1.

Corollary 1.2

Every planar graph G without $C_4$ and $C_6$ has independence number at least $\frac{2|V(G)|}{7}$.

In the rest of this section, we give some definitions and notations that will be used throughout this paper. Denote by d(v) the degree of a vertex v. A k-vertex is a vertex of degree k. A $k^+$-vertex or $k^-$-vertex is a vertex of degree at least or at most k. For a cycle C of a plane graph G, the vertices lying inside or outside of C are denoted by Int(C) or Out(C), respectively. If $Int(C) \ne \emptyset$ and $Out(C) \ne \emptyset$, then C is a separating cycle. Two cycles are called adjacent if they have an edge in common. For a cycle C with a given orientation $\overrightarrow{C}$, and for any $u,v\in V(C)$, we use $u\overrightarrow{C}v$ to denote the consecutive vertices of C from u to v in the direction specified by $\overrightarrow{C}$. For $F\subseteq E(G)$, $G-F$ denotes the resulting graph by deleting all edges of F from G. For $S\subseteq V(G)$, $G-S$ denotes the subgraph induced by $V(G)\setminus S$. For $e\in V(G)$, we simplify $G-\{e\}$ to $G-e$, and for $v\in V(G)$, we simplify $G-\{v\}$ to $G-v$.

2 Lemmas

In this section, we first introduce the definition of a graph to be (L : 2)-colorable, then give some technical lemmas that will be used in the proof of Theorem 1.1.

Let $L=\{L(v): v\in G\}$ be a set of lists, and each list L(v) consists of several elements associated with each vertex v of G. Let $\phi$ be an assignment of 2-subsets of L(v) to each vertex v of G such that for every edge uv of G, the sets $\phi (u)$ and $\phi (v)$ are disjoint. We call such an assignment $\phi$ an (L : 2)-coloring of G, and G is said to be (L : 2)-colorable if G has an (L : 2)-coloring.

Lemma 2.1

A path $P=v_1v_2$ is (L : 2)-colorable if $|L(v_1)|=|L(v_2)|=3$ and $L(v_1) \ne L(v_2)$.

Proof

Since $|L(v_1)|=|L(v_2)|=3$ and $L(v_1) \ne L(v_2)$, there exists $\alpha \in L(v_1)\backslash L(v_2)$. Let $\phi (v_1)$ be a 2-subset of $L(v_1)$ with $\alpha \in \phi (v_1)$, and $\phi (v_2)$ a 2-subset of $L(v_2)\backslash \phi (v_1)$. Then $\phi$ is an (L : 2)-coloring of P. $\square$

Lemma 2.2

A path $P=v_1v_2v_3$ is (L : 2)-colorable if $|L(v_1)|=|L(v_3)|=3$ and $|L(v_2)|=5$. Moreover, for any $i_1\in L(v_1)$, P has an (L : 2)-coloring $\phi$ such that $i_1\in \phi (v_1)$.

Proof

Assume that $L(v_1)=\{i_1,i_2,i_3\}$. Let $\phi (v_1)=\{i_1,i_2\}$ and $L'(v_2)=L(v_2)\backslash \phi (v_1)$. Then $|L'(v_2)| \ge 3$. If $L'(v_2)\not =L(v_3)$, then by Lemma 2.1 we obtain an (L : 2)-coloring of P. If $L'(v_2)=L(v_3)$, then $i_3\in L(v_3)$. In this case, replace $\phi (v_1)$ with $\{i_1,i_3\}$, then we have $|L'(v_2)|\ge 3$ and $L'(v_2)\not =L(v_3)$. By Lemma 2.1, we get an (L : 2)-coloring of P. Thus, P always has an (L : 2)-coloring $\phi$ such that $i_1\in \phi (v_1)$, and so the result follows. $\square$

Corollary 2.3

A path $P=v_1v_2v_3$ has at least two (L : 2)-colorings $\phi$ and $\phi '$ such that $\phi (v_1)\not =\phi '(v_1)$ if $|L(v_1)|=|L(v_3)|=3$ and $|L(v_2)|=5$.

Lemma 2.4

A path $P=v_1v_2v_3v_4$ is (L : 2)-colorable if $|L(v_1)|=|L(v_3)|=|L(v_4)|=3$, $|L(v_2)|=5$ and $L(v_3)\ne L(v_4)$.

Proof

Since $L(v_3)\ne L(v_4)$, there exists $\alpha \in L(v_3)\backslash L(v_4)$. By Lemma 2.2, $v_3v_2v_1$ has an (L : 2)-coloring $\phi$ such that $\alpha \in \phi (v_3)$. Note that $|L(v_4)\backslash \phi (v_3)|\ge 2$, $\phi$ can be extended to an (L : 2)-coloring of P by coloring $v_4$ a 2-subset of $L(v_4)\backslash \phi (v_3)$.    $\square$

Lemma 2.5

A path $P=v_1v_2v_3v_4$ has at least two (L : 2)-colorings $\phi$ and $\phi '$ such that $\phi (v_1)\not =\phi '(v_1)$ if $|L(v_1)|=3$, $|L(v_2)|=4$, $|L(v_3)|=5$ and $|L(v_4)|=3$, or $|L(v_1)|=4$, $|L(v_2)|=3$, $|L(v_3)|=5$ and $|L(v_4)|=3$.

Proof

If $|L(v_1)|=3$, $|L(v_2)|=4$, $|L(v_3)|=5$ and $|L(v_4)|=3$, we let $L(v_2)=\{i,i_1,i_2,i_3\}$ and $i\in L(v_2)\backslash L(v_1)$. Clearly, there is at most one of the three 2-subsets $\{i,i_1\},\{i,i_2\},\{i,i_3\}$, say $\{i,i_3\}$, such that $L(v_3)\backslash \{i,i_3\}=L(v_4)$. Thus, the path $v_2v_3v_4$ has two (L : 2)-colorings $\phi$ and $\phi '$ such that $\phi (v_2)=\{i,i_1\}$ and $\phi '(v_2)=\{i,i_2\}$. Since we can choose two 2-subsets $\phi (v_1)$ and $\phi '(v_1)$ from $L(v_1)\backslash \phi (v_2)$ and $L(v_1)\backslash \phi '(v_2)$, respectively, such that $\phi (v_1)\not =\phi '(v_1)$, both $\phi$ and $\phi '$ can be extended to (L : 2)-colorings of P as required.

If $|L(v_1)|=4$, $|L(v_2)|=3$, $|L(v_3)|=5$ and $|L(v_4)|=3$, then by Corollary 2.3, the path $v_2v_3v_4$ has two (L : 2)-colorings $\phi$ and $\phi '$ such that $\phi (v_2)\not =\phi '(v_2)$. Because we can choose two 2-subsets $\phi (v_1)$ and $\phi '(v_1)$ from $L(v_1)\backslash \phi (v_2)$ and $L(v_1)\backslash \phi '(v_2)$, respectively, such that $\phi (v_1)\not =\phi '(v_1)$, $\phi$ and $\phi '$ can be extended to (L : 2)-colorings of P as required. $\square$

Lemma 2.6

A path $P=v_1v_2v_3v_4v_5v_6$ is (L : 2)-colorable if $|L(v_i)|=3$ for $i=1,3,4,6$, $|L(v_2)|=|L(v_5)|=5$, $L(v_3)\ne L(v_4)$ and $L(v_1)\backslash L(v_2)\ne \emptyset$.

Proof

By Lemma 2.4, the path $v_6v_5v_4v_3$ has an (L : 2)-coloring $\phi$. Since $L(v_1)\backslash L(v_2)\ne \emptyset$, there exists $\alpha \in L(v_1)\backslash L(v_2)$. Let $\phi (v_1)$ be a 2-subset of $L(v_1)$ with $\alpha \in \phi (v_1)$, then we have $|L(v_2)\backslash (\phi (v_1)\cup \phi (v_3))|\ge 2$, and hence $\phi$ can be extended to an (L : 2)-coloring of P by coloring $v_1$ with $\phi (v_1)$ and $v_2$ with a 2-subset of $L(v_2)\backslash (\phi (v_1)\cup \phi (v_3))$. $\square$

3 Proof of Theorem 1.1

We are going to prove a mild strengthening of Theorem 1.1 where the outer face is precolored.

Theorem 3.1

Let G be a planar graph without $C_4$ and $C_6$. Then

• (1) G is (7 : 2)-colorable, and

• (2) Every proper (7 : 2)-coloring of any cycle of length 3, 5, 7 or 8 that respects the chords of the cycle in G can be extended to a proper (7 : 2)-coloring of the whole graph.

If G has no 3-, 5-, 7- or 8-cycles, then since the absence of 4- and 6-cycles, it is 3-colorable, and so (6 : 2)-colorable. Hence we may assume the existence of 3-, 5-, 7- or 8-cycles in Theorem 3.1. Let G be a minimal counter-example to Theorem 3.1 with respect to $|V(G)|+|E(G)|$. That is, G is not (7 : 2)-colorable or G is (7 : 2)-colorable and has a cycle C (|C| may be 3, 5, 7 or 8) such that a (7 : 2)-coloring $\varphi$ of G[V(C)] cannot be extended to a (7 : 2)-coloring of G. By the minimality, $V(G)\ne V(C)$ and C must be a facial cycle. Assume without loss of generality that the face bounded by C is the outer one of G, denoted by $f_0$. Any face other than $f_0$ is called an internal face of G. The vertices of $V(G)-V(C)$ are called internal vertices. The degree, d(f), of a face f is the number of edges in its boundary, cut edges being counted twice. A k-face is a face of length exactly k.

A 3-face is also called a triangle. A vertex is called bad if it is an internal 3-vertex incident with a triangle, or an internal 4-vertex incident with two triangles. For any internal face f, we use $f\cap f_0$ to denote the set of vertices in both f and $f_0$.

In the following proof, we first discuss the properties of the minimal counter-example, and then based on the arguments, we prove Theorem 3.1 by discharging method.

3.1 Basic properties of the minimal counter-example

Since G has no $C_4$ or $C_6$, Lemmas 3.2–3.5 are obvious.

Lemma 3.2

Any triangle is not adjacent to triangles.

Lemma 3.3

Any $C_5$ has no chords and is not adjacent to triangles.

Lemma 3.4

Any $C_7$ has no chords.

Lemma 3.5

Any $C_8$ has no two chords uv such that the length of $u\overrightarrow{C}v$ is two, four or six.

The following lemmas depend on the minimality of G.

Lemma 3.6

G has no separating cycles of lengths 3, 5, 7 or 8.

Proof

Suppose that $C_0$ is a separating cycle of G with $|C_0|\in \{3,5,7,8\}$ and C is in $Out(C_0)$. By the minimality, $\varphi$ can be extended to a (7 : 2)-coloring of $G-Int(C_0)$, and this extended (7 : 2)-coloring on $C_0$ can also be extended to a (7 : 2)-coloring of $G-Out(C_0)$, which is a contradiction. $\square$

Lemma 3.7

C has no chords.

Proof

Suppose that C has a chord $v_1v_2$. Obviously, $\varphi$ is also a (7 : 2)-coloring of $G[V(C)]-v_1v_2$. By the minimality of G, $\varphi$ can be extended to a (7 : 2)-coloring of $G - v_1v_2$. Note that the chord $v_1v_2$ implies that $\varphi (v_1) \cap \varphi (v_2)=\emptyset$, we can extend $\varphi$ to a (7 : 2)-coloring of G, a contradiction. $\square$

Lemma 3.8

G is 2-connected.

Proof

By the minimality, G is connected. Suppose that G has a cut vertex v and $G_1$ and $G_2$ are two components of $G-v$. Assume that C is in $G-V(G_2)$. By the minimality of G, we can extend $\varphi$ to a (7 : 2)-coloring of $G-V(G_2)$, and $G-V(G_1)$ has a (7 : 2)-coloring $\varphi '$. Exchange the colors such that $\varphi '(v)=\varphi (v)$, then $\varphi$ together with $\varphi '$ is a (7 : 2)-coloring of G. $\square$

By Lemma 3.8, we have the following corollary.

Corollary 3.9

$\delta (G)\ge 2$.

Let H be a subgraph of G and $\phi$ be any (7 : 2)-coloring of $G-V(H)$ with the color set $\{1,2,\ldots ,7\}$ and

$$\begin{aligned} \Phi (v)=\bigcup _{u\in N(v)\backslash V(H)}\phi (u) \end{aligned}$$

for any $v\in V(H)$, where N(v) is the set of neighbors of v in G.

Set

$$\begin{aligned} L(v)=\{1,2,\ldots ,7\} \backslash \Phi (v)~and~\ell (v)=|L(v)|. \end{aligned}$$

These notations will be used throughout the rest of this paper.

In what follows, we discuss some subgraphs that cannot appear in G.

Lemma 3.10

Each 2-vertex belongs to C.

Proof

If there is some $v\in Int(C)$ with $d(v)=2$, then by the minimality of G, we can extend $\varphi$ to $G-v$. Since $\ell (v) \ge 3$, $\varphi$ can be extended to v by coloring v with any 2-subset of L(v), a contradiction. $\square$

Lemma 3.11

G has no path $v_1zv_2$ such that $v_1$, $v_2$ are not consecutive on C and $z \in Int(C)$.

Proof

Suppose that G has a path $v_1zv_2$ such that $v_1$, $v_2$ are not consecutive on C and $z \in Int(C)$. Then $C=C_8$ as shown in Fig. 1a, due to $|C|\le 8$ and G has no $C_4$ or $C_6$. By Lemmas 3.3, 3.4 and 3.6, $d(z)=2$ which contradicts Lemma 3.10. $\square$

Fig. 1

Two forbidden subgraphs

Lemma 3.12

Suppose $v_1z_1z_2v_2$ is a path with $v_1,v_2 \in V(C)$ and $z_1,z_2 \in Int(C)$. Then $v_1$ and $v_2$ have a common neighbor $v \in V(C)$.

Proof

Suppose that $v_1$ and $v_2$ have no common neighbors in C. Since G has no $C_4$ or $C_6$, we have $|v_1\overrightarrow{C}v_2|\ge 3$ and $|v_2\overrightarrow{C}v_1|\ge 3$. Because $|C|\le 8$, $C=C_8$ as shown in Fig. 1b. By Lemmas 3.3, 3.4 and 3.6, $d(z_1)=d(z_2)=2$ which contradicts Lemma 3.10. $\square$

Lemma 3.13

Int(C) has no induced path $v_1v_2v_3$ such that $d(v_i) =3$ for $i=1,2,3$.

Proof

If Int(C) has such a path $v_1v_2v_3$, then by the minimality of G, $\varphi$ can be extended to $G-\{v_1,v_2,v_3\}$. Since $d(v_i) = 3$ for $i=1,2,3$, $\ell (v_i)\ge 3$ for $i=1,3$ and $\ell (v_2)=5$. By Lemma 2.2, $\varphi$ can also be extended to a (7 : 2)-coloring of G, a contradiction. $\square$

Lemma 3.14

Int(C) has no induced path $v_1v_2v_3v_4$ such that $d(v_1) = d(v_2) = d(v_4) = 3$ and $d(v_3)=4$.

Proof

Suppose to the contrary that $v_1v_2v_3v_4$ is such a path. Then $\varphi$ can be extended to $G'=G-\{v_1,v_2\}$ by the minimality of G. Obviously, this (7 : 2)-coloring of $G'$ is also a (7 : 2)-coloring of $G''=G'-\{v_3,v_4\}$. Since $v_3v_4\in E(G')$ and $v_3,v_4$ are of degree 3 in $G'$, $L(v_3)\not =L(v_4)$ if $l(v_3)=l(v_4)=3$ in this (7 : 2)-coloring of $G''$. By the assumption, we find $\ell (v_i)\ge 3$ for $i=1,3,4$ and $\ell (v_2)=5$ in the (7 : 2)-coloring of $G''$. By Lemmas 2.4 or 2.5, $\varphi$ can be extended to a (7 : 2)-coloring of G, a contradiction. $\square$

3.2 Discharging

Euler formula $|V(G)|-|E(G)|+|F(G)|=2$ for plane graph G can be rewritten as

$$\begin{aligned} \sum _{v \in V(G)} (d(v)-4)+\sum _{f \in F(G)} (d(f)-4)=-8. \end{aligned}$$

Set the initial charge$ch(v)=d(v)-4$ for every vertex v, the initial charge$ch(f)=d(f)-4$ for every face $f \ne f_0$ and put the initial charge$ch(f_0)=d(f_0)+4$. Clearly,

$$\begin{aligned} \sum _{x \in V(G) \cup F(G)} ch(x)=0. \end{aligned}$$

3.2.1 Discharging rules

We reassign the charge of each vertex according to the following rules:

• R1 The outer face $f_0$ sends $\frac{4}{3}$ to each vertex of C.

• R2 Each triangle receives $\frac{1}{3}$ from each incident vertex.

• R3 Each internal non-triangular face f sends to each incident vertex v:

  • (a) $\frac{2}{3}$ for $d(v)=2$.

  • (b) for $d(v)=3$ and v is internal:

    • (b1) $\frac{2}{3}$ if v is bad,

    • (b2) $\frac{1}{3}$ if v is not bad.

  • (c) for $d(v)=4$ and v is internal:

    • (c1) $\frac{1}{3}$ if v is bad,

    • (c2) $\frac{1}{9}$ if v is incident with one triangle.

• R4 Each internal 5-vertex v sends to each incident non-triangular face:

  • (a) $\frac{1}{5}$ if v is not incident with triangles,

  • (b) $\frac{1}{6}$ if v is incident with one triangle,

  • (c) $\frac{1}{9}$ if v is incident with two triangles.

• R5 Each internal $6^+$-vertex v sends $\frac{1}{3}$ to every incident internal face.

• R6 If $v\in V( C)$, $d(v)=3$ and v is not incident with triangles, then v sends $\frac{1}{6}$ to each of the two internal faces incident with v.

• R7 If $v\in V( C)$ and $d(v) \ge 4$, then v sends $\frac{1}{3}$ to every incident internal face.

Let $ch^*$ denote the final charge after performing charge redistribution using rules R1–R7.

3.2.2 Final charges of vertices

Lemma 3.15

For any $v \in V(G)$, we have $ch^{*}(v) \ge 0$.

Proof

Let v be any vertex of G. Then $d(v)\ge 2$ by Corollary 3.9.

If $d(v)=2$, then $v \in V( C)$ by Lemma 3.10, and so v receives $\frac{4}{3}$ from $f_0$ by R1. Since C has no chords by Lemma 3.7, v is not incident with triangles, and so v receives $\frac{2}{3}$ from the internal face incident with it by R3. Therefore, $ch^{*}(v)=2-4+\frac{4}{3}+\frac{2}{3}=0$.

If $d(v)=3$, then v is incident with at most one triangle by Lemma 3.2. If $v \in V( C)$, then v receives $\frac{4}{3}$ from $f_0$ by R1, and sends totally $\frac{1}{3}$ to one internal triangle or two internal non-triangular faces by R2 or R6. Thus, $ch^{*}(v)=3-4+\frac{4}{3}-\frac{1}{3}=0$. Consider $v \notin V( C)$. If v is not bad, then v receives $\frac{1}{3}$ from each face incident with v by R3. Thus, $ch^{*}(v)=3-4+3\times \frac{1}{3}=0$. If v is bad, then v receives $\frac{2}{3}$ from each non-triangular face incident with v by R3, and sends $\frac{1}{3}$ to the triangle incident with it by R2. Thus, $ch^{*}(v)=3-4+2\times \frac{2}{3}-\frac{1}{3}=0$.

If $d(v)=4$, then v is incident with at most two triangles by Lemma 3.2. If $v \in V( C)$, then v receives $\frac{4}{3}$ from $f_0$ by R1, and sends away $\frac{1}{3}$ to each incident internal face by R7. Hence, $ch^{*}(v)=4-4+\frac{4}{3}-3\times \frac{1}{3}=\frac{1}{3}>0$. Assume $v \notin V( C)$. If v is bad, then v receives $\frac{1}{3}$ from each incident non-triangular face by R3, and sends away $\frac{1}{3}$ to each triangle incident with it by R2. Thus, $ch^{*}(v)=4-4+2\times \frac{1}{3}-2\times \frac{1}{3}=0$. If v is incident with one triangle, then v receives $3\times \frac{1}{9}$ by R3, and sends away $\frac{1}{3}$ by R2, so $ch^{*}(v)=4-4+3\times \frac{1}{9}- \frac{1}{3}= 0$. If v is not incident with triangles, then $ch^{*}(v)=ch(v)=0$.

If $d(v)=5$, then v is incident with at most two triangles by Lemma 3.2. If $v \in V( C)$, then v receives $\frac{4}{3}$ from $f_0$ by R1, and sends $\frac{1}{3}$ to each incident internal face incident with it by R7. Thus, $ch^{*}(v)=5-4+\frac{4}{3}-4\times \frac{1}{3}=1>0$. Suppose $v \notin V(C)$. If v is incident with two triangles, then v sends $\frac{1}{3}$ to each of the two triangles by R2, and sends $\frac{1}{9}$ to each non-triangular face incident with it by R4. Thus $ch^{*}(v)=5-4-2\times \frac{1}{3}-3\times \frac{1}{9}=0$. If v is incident with one triangle, then v sends $\frac{1}{3}$ to this triangle by R2, and sends $\frac{1}{6}$ to each non-triangular face incident it by R4. Hence, $ch^{*}(v)=5-4-\frac{1}{3}-4\times \frac{1}{6}=0$. If v is not incident with triangles, then v sends $\frac{1}{5}$ to each face incident with it by R4, and so $ch^{*}(v)=5-4-5\times \frac{1}{5}=0$.

If $d(v) \ge 6$, then by R5 and R7, v sends totally at most $\frac{1}{3}d(v)$ to all the internal faces incident with it, and hence we have $ch^{*}(v) \ge d(v)-4-\frac{1}{3}d(v)=\frac{2(d(v)-6)}{3} \ge 0$. $\square$

3.2.3 Final charges of faces

Lemma 3.16

$ch^{*}(f_0)>0.$

Proof

Recall that $ch(f_0)=d(f_0)+4$, by R1, we have $ch^{*}(f_0)=d(f_0)+4-d(f_0)\times \frac{4}{3}=\frac{12-d(f_0)}{3}\ge \frac{12-8}{3}=\frac{4}{3}>0$. $\square$

Lemma 3.17

Let f be an internal face of G. If $d(f)=3$ or $d(f) \ge 8$, then $ch^{*}(f) {\ge } 0$.

Proof

If $d(f)=3$, then by R2, f receives $\frac{1}{3}$ from each of its three incident vertices, and so $ch^{*}(f)=3-4+3\times \frac{1}{3} = 0$. Thus we may assume that $d(f) \ge 8$.

If $|f\cap f_0|=0$, then f is incident with at most $\frac{2}{3}d(f)$ vertices of degree 3 by Lemma 3.13. Since f sends to each incident 3-vertex at most $\frac{2}{3}$ and each incident $4^+$-vertex at most $\frac{1}{3}$ by R3, we have $ch^{*}(f)\ge d(f)-4-\frac{2d(f)}{3}\times \frac{2}{3}-\frac{d(f)}{3}\times \frac{1}{3}=\frac{4d(f)}{9}-4\ge 0$ if $d(f)\ge 9$. For $d(f)=8$, f is incident with at most five 3-vertices. By Lemma 3.14, if f is incident with five 3-vertices, then the other three vertices must be $5^+$-vertices. By R3, f sends away at most $5\times \frac{2}{3}$, and hence $ch^{*}(f)\ge 8-4-5\times \frac{2}{3}=\frac{2}{3}>0$. If f is incident with at most four 3-vertices, then by R3, $ch^{*}(f)\ge 8-4-4\times \frac{2}{3}-4\times \frac{1}{3}=0$. If $|f\cap f_0|=1$, then the vertex in $f\cap f_0$ must be a $4^+$-vertex, and so f can receive $\frac{1}{3}$ from this vertex by R7. By Lemma 3.13, f is incident with at least two internal $4^+$-vertices. By R3, f sends to each incident 3-vertex at most $\frac{2}{3}$ and each incident $4^+$-vertex at most $\frac{1}{3}$, and so $ch^{*}(f)\ge d(f)-4+\frac{1}{3}-(d(f)-3)\times \frac{2}{3}-2\times \frac{1}{3}=\frac{d(f)-7}{3}>0$. If $|f\cap f_0|\ge 2$, then $f\cap f_0$ has at least two $3^+$-vertices and f sends nothing to them. By R3, f sends to any other incident vertex at most $\frac{2}{3}$, and so $ch^{*}(f)=d(f)-4-(d(f)-2)\times \frac{2}{3}=\frac{d(f)-8}{3}\ge 0$. $\square$

Lemma 3.18

Let f be an internal 5-face, then $ch^{*}(f) \ge 0$.

Proof

Since C has no chords by Lemma 3.7, we have $|f\cap f_0|\le 4$. If $|f\cap f_0|=4$, the only vertex $u\notin f\cap f_0$ together its two neighbors $v_1,v_2$ in $f\cap f_0$ form a path $v_1uv_2$ with $u\in Int(C)$. Because G has no $C_4$, we have $v_1v_2\notin E(C)$, which contradicts Lemma 3.11. So we assume that $|f\cap f_0|\le 3$. Since f is not adjacent to triangles by Lemma 3.3, each internal vertex incident with f is not bad. If $|f\cap f_0|\ge 2$, then $f\cap f_0$ has at least two $3^+$-vertices and at most one 2-vertex. Since f is not adjacent to triangles by Lemma 3.3, each $3^+$-vertex of $f\cap f_0$ can send $\frac{1}{6}$ to f by R6. Thus, by R3, we have $ch^{*}(f)\ge 5-4+2\times \frac{1}{6}-\frac{2}{3}-2\times \frac{1}{3}= 0$ if $f\cap f_0$ has a 2-vertex, and $ch^{*}(f)\ge 5-4+2\times \frac{1}{6}-3\times \frac{1}{3}=\frac{1}{3}>0$ otherwise. If $|f\cap f_0|=1$, then this vertex is a $4^+$-vertex and can send $\frac{1}{3}$ to f by R7. By Lemma 3.13, f is incident with at most three internal 3-vertices. Thus, we have $ch^{*}(f)\ge 5-4+\frac{1}{3}-3\times \frac{1}{3}=\frac{1}{3}>0$ by Lemma 3.14 and R3. If $|f\cap f_0|=0$, then f is incident with at most three 3-vertices by Lemma 3.13. Thus, by Lemma 3.14 and R3, we have $ch^{*}(f)\ge 5-4-3\times \frac{1}{3}=0$. $\square$

Lemma 3.19

Let f be an internal 7-face with $f\cap f_0\not =\emptyset$, then $ch^{*}(f) \ge 0$.

Proof

Since C has no chords by Lemma 3.7, $t=|f\cap f_0|\le 6$. If $t=6$, then the only vertex $u\notin f\cap f_0$ together its two neighbors $v_1,v_2$ in $f\cap f_0$ form a path $v_1uv_2$ with $u\in Int(C)$. Since G has no $C_6$, $v_1v_2\notin E(C)$, which contradicts Lemma 3.11. If $2\le t\le 5$, then $f\cap f_0$ has at least two $3^+$-vertices. If $f\cap f_0$ has a $4^+$-vertex, then by R7, this vertex can send $\frac{1}{3}$ to f. Note that f sends away at most $\frac{2}{3}$ to each internal vertex and each 2-vertex by R3, we have $ch^{*}(f)\ge 7-4+\frac{1}{3}-5\times \frac{2}{3}=0$. Thus we may assume each vertex of $f\cap f_0$ is a $3^-$-vertex. In this case, all vertices of $f\cap f_0$ are consecutive on C. Assume that the face f is bounded by the cycle $v_1v_2\cdots v_7$ and $v_1,\ldots ,v_t$ are in $f\cap f_0$. If $t=5$, then G has a path $v_5v_6v_7v_1$ with $v_6,v_7\in Int(C)$. By Lemma 3.14, $v_1$ and $v_5$ have a common neighbor v on C, which means $v_1v_2v_3v_4v_5v$ is a $C_6$, a contradiction. If $2\le t\le 4$, then by Lemma 3.13, at least one of $v_5,v_6,v_7$ is $4^+$-vertex. Thus, $ch^*(f)\ge 7-4-\frac{1}{3}-4\times \frac{2}{3}=0$. If $t=1$, then the only vertex in $f\cap f_0$ is a $4^+$-vertex and can send $\frac{1}{3}$ to f by R7. By Lemma 3.13, f is incident with at most four 3-vertices. Since f sends to each 3-vertex at most $\frac{2}{3}$ and each 4-vertex at most $\frac{1}{3}$ by R3, we have $ch^{*}(f)\ge 7-4+\frac{1}{3}-4\times \frac{2}{3}-2\times \frac{1}{3}=0$. $\square$

Lemma 3.20

Let f be a 7-face with $f\cap f_0=\emptyset$, then $ch^{*}(f) \ge 0$.

Proof

Assume that f is bounded by the cycle $v_1v_2\cdots v_7$ and $S=\{v_1,v_2,\ldots ,v_7\}$.

By Lemma 3.13, S has at most four 3-vertices. If S has at most two 3-vertices, then by R3, $ch^{*}(f) \ge 7-4-2\times \frac{2}{3}-5\times \frac{1}{3}=0$, and so we may assume that S has at least three 3-vertices.

Suppose that S has exactly three 3-vertices. If S has a $5^+$-vertex, then by R4, the vertex can send at least $\frac{1}{9}$ to f, and so $ch^{*}(f) \ge 7-4-3\times \frac{2}{3}-3\times \frac{1}{3}+\frac{1}{9}=\frac{1}{9}>0$. Thus, S has four 4-vertices. In such a case, there exist two consecutive 4-vertices on the cycle $v_1v_2\cdots v_7$. Assume that $d(v_6)=d(v_7)=4$. By Lemmas 3.13 and 3.14, $d(v_1)=d(v_5)=3$. If S has at least two 4-vertices not being bad, then $ch^{*}(f) \ge 7-4-3\times \frac{2}{3}-2\times \frac{1}{3}-2\times \frac{1}{9}=\frac{1}{9}>0$. Thus we can assume that S has at most one 4-vertex not being bad. If $d(v_2)=d(v_4)=4$, then one of $v_2,v_7$ is not bad because $d(v_1)=3$, and one of $v_4,v_6$ is not bad since $d(v_5)=3$, a contradiction. Thus, by symmetry, we assume that $d(v_2)=3$ and $d(v_3)=d(v_4)=4$. By the arguments above, the subgraph, induced by S and its all neighbors $v_8,\ldots ,v_{13}$ in Out(f), can be shown as in Fig. 2. In the following, we show this cannot occur by the minimality of G, and hence $ch^*(f) \ge 0$ if S has three 3-vertices.

Fig. 2

S has three 3-vertices and four 4-vertices

It is easy to check $v_i \ne v_j$ for $8 \le i<j \le 13$ since G has no $C_4$ or $C_6$.

Let $G'=G-S+\{v_8v_{10},v_{11}v_{13}\}$. Then $G'$ is still a plane graph.

Claim 3.1

$G'$ has no $C_4$ or $C_6$ and keeps the proper coloring $\varphi$ on C.

Proof

Suppose to the contrary that K is a $C_4$ or $C_6$ of $G'$. Since G has no $C_4$ or $C_6$, $v_8v_{13}$, $v_8v_{11}$, $v_{10}v_{13}$, $v_{10}v_{11}\notin E(G)$ and $N(v_8)\cap N(v_{13})=N(v_8)\cap N(v_{11})=\emptyset$, which implies that K cannot contain both $v_8v_{10}$ and $v_{11}v_{13}$. If K contains $v_8v_{10}$ or $v_{11}v_{13}$, then $v_6v_7v_{10}\overrightarrow{K}v_8$ or $v_3v_4v_{13}\overrightarrow{K}v_{11}$ is a $C_6$ or a $C_8$ in G separating $v_9$ and $v_i$ for some $i\in \{1,2,3,4,5\}$, or $v_3$ and $v_j$ for some $j\in \{1,2,5,6,7\}$, a contradiction. Therefore, $G'$ has no $C_4$ or $C_6$.

If $v_8,v_{10}\in V(C)$ or $v_{11},v_{13}\in V(C)$, then by Lemma 3.12, there exist $u_1$ or $u_2$ in V(C) such that $u_1v_8,u_1v_{10}\in E(C)$ or $u_2v_{11},u_2v_{13}\in E(C)$, which means $u_1v_8v_6v_7v_1v_{10}$ or $u_2v_{11}v_2v_3v_4v_{13}$ is a $C_6$ in G, a contradiction. So $\varphi$ is also a proper coloring on C in $G'$.

By Claim 3.1 and the minimality of G, we can extend $\varphi$ to a (7 : 2)-coloring of $G'$.

Since $d(v_i)=3$ for $i=1,2,5$ and $d(v_j)=4$ for $j=3,4,6,7$, we have $\ell (v_i)=5$ for $i=1,2,5$ and $\ell (v_i)\ge 3$ for $i=3,4,6,7$. Since $\varphi (v_8)\cap \varphi (v_{10})=\emptyset$ and $d(v_6)=d(v_7)=4$, we can choose a 2-subset $A\subseteq L(v_7)$ such that $|L'(v_6)|=|L(v_6)\backslash A|\ge 3$. Let $L'(v_i)=L(v_i)$ for $i=3,4,5$. If $\ell (v_4)\ge 4$ or $\ell (v_3)\ge 4$, then by Lemma 2.5, $v_3v_4v_5v_6$ has an $(L':2)$-coloring $\phi$ such that $L(v_1)\backslash A\not =L(v_2)\backslash \phi (v_3)$. By Lemma 2.1, $\varphi$ can be extended to a (7 : 2)-coloring of G. Thus we may assume that $\ell (v_3)=\ell (v_4)=3$. Similarly, because $\varphi (v_{11})\cap \varphi (v_{13})=\emptyset$ and $d(v_3)=d(v_4)=4$, we can choose a 2-subset $A\subseteq L(v_3)$ such that $|L'(v_4)|=|L(v_4)\backslash A|\ge 3$. Let $L'(v_i)=L(v_i)$ for $i=5,6,7$. If $\ell (v_6)\ge 4$ or $\ell (v_7)\ge 4$, then by Lemma 2.5, $v_7v_6v_5v_4$ has an $(L':2)$-coloring $\phi$ such that $L(v_1)\backslash \phi (v_7)\not =L(v_2)\backslash A$. By Lemma 2.1, $\varphi$ can be extended to a (7 : 2)-coloring of G. Thus we may assume that $\ell (v_6)=\ell (v_7)=3$. Therefore, we have $\ell (v_i)=3$ for $i=3,4,6,7$. Because $\varphi (v_{11})\cap \varphi (v_{13})=\emptyset$ and $d(v_3)=d(v_4)=4$, and $\varphi (v_8)\cap \varphi (v_{10})=\emptyset$ and $d(v_6)=d(v_7)=4$, we have $|L(v_3)\cap L(v_4)|=|L(v_6)\cap L(v_7)|=1$.

Claim 3.2

$\varphi$ can be extended to $P=v_3v_4v_5v_6v_7$ such that $L(v_2)\backslash \varphi (v_3)\ne L(v_1)\backslash \varphi (v_7)$.

Proof

Suppose that $\alpha \in L(v_4)\backslash L(v_5)$. Let $A_1$ be a 2-subset of $L(v_4)$ with $\alpha \in A_1$, $A_2$ a 2-subset of $L(v_3)\backslash L(v_4)$, $A_3=L(v_6)\backslash L(v_7)$, $A_4$ a 2-subset of $L(v_7)$ such that $L(v_1)\backslash A_4\not =L(v_2)\backslash A_2$, and $A_5$ a 2-subset of $L(v_5)\backslash (A_1\cup A_3)$. Set $\varphi (v_4)=A_1$, $\varphi (v_3)=A_2$, $\varphi (v_6)=A_3$, $\varphi (v_7)=A_4$ and $\varphi (v_5)=A_5$, then $\varphi$ is extended to P as required. Thus, we may assume that $L(v_4)\subset L(v_5)$. By the symmetry of $v_4$ and $v_6$, $L(v_6)\subset L(v_5)$.

Since $\ell (v_4)=\ell (v_6)=3$ and $\ell (v_5)=5$, we may assume that $\beta \in L(v_4)\cap L(v_6).$

Let $L(v_3)\cap L(v_4)=\{\alpha \}$. If $\alpha \not =\beta$, then $\beta \notin L(v_3)$ as $|L(v_3)\cap L(v_4)|=1$. Let $A_1$ be a 2-subset of $L(v_6)$ with $\beta \in A_1$, $A_2$ a 2-subset of $L(v_7)\backslash A_1$, $A_3$ a 2-subset of $L(v_3)$ such that $L(v_2)\backslash A_3\ne L(v_1)\backslash A_2$, and $A_4$ a 2-subset of $L(v_4)\backslash A_3$ with $\beta \in A_4$. Then $\varphi$ can be extended to P as required by coloring $v_6$ with $A_1$, $v_7$ with $A_2$, $v_3$ with $A_3$, $v_4$ with $A_4$ and $v_5$ with a 2-subset of $L(v_5)\backslash (A_1\cup A_4)$. Thus, by symmetry, we may assume that $L(v_3)\cap L(v_4)=L(v_4)\cap L(v_6)=L(v_6)\cap L(v_7)=\{\alpha \}$.

By the arguments above, we may assume that $\alpha =7$, $L(v_5)=\{1,2,3,4,7\}$, $L(v_4)=\{1,2,7\}$ and $L(v_6)=\{3,4,7\}$. Since $\ell (v_5)=5$ and $\ell (v_6)=3$, we have $\varphi (v_8)=\{5,6\}$ and $\varphi (v_9)=\{1,2\}$. Since $L(v_7)\cap L(v_6)=\{7\}$ and $\varphi (v_9)=\{1,2\}$, we have $L(v_7)=\{5,6,7\}$, and so $\varphi (v_{10})=\{3,4\}$ and $L(v_1)=\{1,2,5,6,7\}$. Note that $\varphi (v_{12})\cup \varphi (v_{13})=\{3,4,5,6\}$ and $\ell (v_3)=3$, we can deduce $\varphi (v_{11})=\{1,2\}$ and $L(v_2)=\{3,4,5,6,7\}$. Thus $\varphi$ can be extended to P as required by coloring $v_3$ with $L(v_3)\backslash \{7\}$, $v_4$ with $\{1,7\}$, $v_5$ with $\{2,4\}$, $v_6$ with $\{3,7\}$, $v_7$ with $\{5,6\}$. $\square$

By Claim 3.2 and Lemma 2.1, $\varphi$ can be extended to a (7 : 2)-coloring of G, which is a contradiction.

Now, we are left to consider the case when S has four 3-vertices. If S has a $6^+$-vertex, then by R3 and R5, $ch^{*}(f) \ge 7-4+\frac{1}{3}-4\times \frac{2}{3}-2\times \frac{1}{3}=0$. If S has two $5^+$-vertices, then by R3 and R4, $ch^{*}(f) \ge 7-4+2\times \frac{1}{9}-4\times \frac{2}{3}-1\times \frac{1}{3}=\frac{2}{9}>0$. Thus, by Lemma 3.14, S contains one 5-vertex and two 4-vertices. By Lemmas 3.13 and 3.14, we may assume that $d(v_1)=d(v_2)=4$, $d(v_3)=d(v_4)=d(v_6)=d(v_7)=3$ and $d(v_5)=5$. If S has a 3-vertex not being bad, then by R3, $ch^{*}(f)>7-4-3\times \frac{2}{3}-3\times \frac{1}{3}=0$, and so each 3-vertex is bad. This implies that both $v_1$ and $v_2$ are bad or both not. If both $v_1$ and $v_2$ are not bad, then by R3 and R4, $ch^{*}(f)\ge 7-4+\frac{1}{9}-4\times \frac{2}{3}-2\times \frac{1}{9}=\frac{2}{9}>0$. Therefore, we may assume that $v_i$ is bad for $i\not =5$. Thus, the subgraph, induced by S and its all neighbors $v_8,\ldots ,v_{13}$ in Out(f), can be shown as in Fig. 3. In the following, we show this cannot occur by the minimality of G, and hence $ch^*(f)\ge 0$ if S has four 3-vertices.

It is easy to check $v_i \ne v_j$ for $8\le i<j \le 13$ since G has no $C_4$ or $C_6$.

Let $G'=G-(S\backslash \{v_5\})+\{v_8v_{10},v_{11}v_{12}\}$. Then $G'$ is still a plane graph.

Claim 3.3

$G'$ has no $C_4$ or $C_6$ and keeps the proper coloring $\varphi$ on C.

Proof

Assume that K is a $C_4$ or $C_6$ of $G'$. Since G has no $C_4$ or $C_6$, $v_{11}v_8$, $v_{11}v_{10}$, $v_{12}v_8$, $v_{12}v_{10}\notin E(G)$ and $N(v_{12})\cap N(v_8)= N(v_{12})\cap N(v_{10})=\emptyset$. Thus, K cannot contain both $v_8v_{10}$ and $v_{11}v_{12}$. If K contains $v_8v_{10}$, then $v_1v_2v_{10}\overrightarrow{K}v_8$ is a $C_6$ or a $C_8$ separating $v_9$ and $v_i$ for some $i\in \{3,4,5,6,7\}$ in G, a contradiction. If K contains $v_{11}v_{12}$, then $v_5v_{12}\overrightarrow{K}v_{11}$ is a $C_5$ or $C_7$ separating $v_4$ and $v_{13}$, which contradicts Lemma 3.6.

If $v_8,v_{10}\in V(C)$ or $v_{11},v_{12}\in V(C)$, then by Lemma 3.12, there exist $u_1$ or $u_2$ in V(C) such that $u_1v_8,u_1v_{10}\in E(C)$ or $u_2v_{11},u_2v_{12}\in E(C)$, which means $u_1v_8v_7v_1v_2v_{10}$ or $u_2v_{11}v_4v_5v_6v_{12}$ is a $C_6$ in G, a contradiction. So $\varphi$ is also a proper coloring on C in $G'$. $\square$

Fig. 3

S has four 3-vertices, two 4-vertices and one 5-vertex

By Claim 3.3 and the minimality of G, we can extend $\varphi$ to a (7 : 2)-coloring of $G'$.

Since $d(v_3)=d(v_7)=3$, $\ell (v_3)=\ell (v_7)=5$. Note that $\varphi (v_{11})\cap \varphi (v_{12})=\emptyset$ and $d(v_4)=d(v_6)=3$, we have $\ell (v_4)=\ell (v_6)=3$ and $|L(v_4)\cap L(v_6)|=1$. Because $\varphi (v_{8})\cap \varphi (v_{10})=\emptyset$ and $d(v_1)=d(v_2)=4$, we have $\ell (v_i)\ge 3$ for $i=1,2$ and $L(v_1)\not =L(v_2)$. If $L(v_4)\backslash L(v_3)\not =\emptyset$ or $L(v_6)\backslash L(v_7)\not =\emptyset$, then by Lemma 2.6, the path $v_6v_7v_1v_2v_3v_4$ is (L : 2)-colorable, and hence $\varphi$ can be extended to a (7 : 2)-coloring of G. So we can assume $L(v_4)\subset L(v_3)$ and $L(v_6)\subset L(v_7)$. Note that $L(v_2)\subset L(v_3)$ and $L(v_1)\subset L(v_7)$, we have $|L(v_2)\cap L(v_4)|\ge 1$ and $|L(v_6)\cap L(v_1)|\ge 1$.

Claim 3.4

There exist $\alpha \in L(v_2)\cap L(v_4)$ and $\beta \in L(v_1)\cap L(v_6)$ such that $\alpha \ne \beta$.

Proof

If $\ell (v_1)\ge 4$ or $\ell (v_2)\ge 4$, then since $L(v_1)\cup L(v_6)\subseteq L(v_7)$ and $L(v_2)\cup L(v_4)\subseteq L(v_3)$, we have $|L(v_1)\cap L(v_6)|\ge 2$ or $|L(v_2)\cap L(v_4)|\ge 2$, and hence the result holds.

Let now $\ell (v_1)=\ell (v_2)=3$. Suppose to the contrary $L(v_2)\cap L(v_4)=L(v_1)\cap L(v_6)=\{7\}$. Set $L(v_2)=\{1,2,7\}$ and $L(v_4)=\{3,4,7\}$. Then $L(v_3)=\{1,2,3,4,7\}$, which implies that $\varphi (v_{10})=\{5,6\}$ and $\varphi (v_{9})=\{3,4\}$. Noting that $\ell (v_1)=3$ and $\varphi (v_8)\cap \varphi (v_{10})=\emptyset$, we have $\varphi (v_8)=\{1,2\}$, and hence $L(v_7)=\{3,4,5,6,7\}$, $L(v_1)=\{5,6,7\}$. Since $\varphi (v_{11})\cap \varphi (v_{12})=\emptyset$ and $L(v_4)=\{3,4,7\}$, we can deduce that $\varphi (v_{12})=\{3,4\}$, and so $L(v_6)=\{5,6,7\}$. This is a contradiction since $L(v_1)\cap L(v_6)=\{5,6,7\}$. $\square$

By Claim 3.4, we let $\alpha \in L(v_2)\cap L(v_4)$ and $\beta \in L(v_1)\cap L(v_6)$ such that $\alpha \ne \beta$. By symmetry, we assume that $\ell (v_1)\ge \ell (v_2)$. Let $A_1$ be a 2-subset of $L(v_2)$ with $\alpha \in A_1$ and $\beta \notin A_1$. Noting that $\ell (v_1)\ge \ell (v_2)\ge 3$ and if $\ell (v_1)=3$, then $|L(v_1)\cap L(v_2)|=1$, we can always choose a 2-subset $A_2$ of $L(v_1)\backslash A_1$ with $\beta \in A_2$. Let $A_3$ be a 2-subset of $L(v_4)$ with $\alpha \in A_3$ and $A_4$ a 2-subset of $L(v_6)$ with $\beta \in A_4$. Then $\varphi$ can be extended to $v_4v_3v_2v_1v_7v_6$ by coloring $v_2$ with $A_1$, $v_1$ with $A_2$, $v_4$ with $A_3$, $v_6$ with $A_4$, $v_3$ with a 2-subset of $L(v_3)\backslash (A_1\cup A_3)$, and $v_7$ with a 2-subset of $L(v_7)\backslash (A_2\cup A_4)$, a contradiction. $\square$

3.2.4 The contradiction

Since the discharging rules only move the charges around, by Lemma 3.15 and 3.16–3.20 , we have

$$\begin{aligned} 0=\sum _{x \in V(G) \cup F(G)} ch(x)=\sum _{x \in V(G) \cup F(G)} ch^*(x)>0. \end{aligned}$$

This contradiction completes the proof of Theorem 3.1.