# A renewal approach to prove
the Four Color Theorem unplugged
Part III:
Diamond routes, canal lines and $\Sigma$-adjustments

Shu-Chung Liu  Institute of Learning Sciences and Technologies, National Tsing
Hua University, Hsinchu, Taiwan<EMAIL_ADDRESS>
###### Abstract.

This is the last part of three episodes to demonstrate a renewal approach for
proving the Four Color Theorem without checking by a computer. The first and
the second episodes have subtitles: “RGB-tilings on maximal planar graphs” and
“R/G/B Kempe chains in an extremum non-4-colorable MPG,” where R/G/B stand for
red, green and blue colors to paint on edges and an MPG stands for a maximal
planar graph. We focus on an extremum non-4-colorable MPG $EP$ in the whole
paper. In this part we introduce three tools based on RGB-tilings. They are
diamond routes, normal and generalized canal lines or rings and
$\Sigma$-adjustments. Using these tools, we show a major result of this paper:
no four vertices of degree 5 form a diamond in any extremum $EP$.

###### Key words and phrases:

Four Color Theorem; Kempe chain; edge-coloring; RGB-tiling; diamond route;
canal line; $\Sigma$-adjustment

###### 2020 Mathematics Subject Classification:

Primary 05C10; 05C15

##  14\. Diamond routes

This section and the next one are independent. We introduce a method to build
a green (or red/blue) tiling on an MPG step by step. At the beginning of this
introduction, we shall first assume the existence of a green tiling. Given an
MPG or a semi-MPG, say $M$, with a green tiling
$T_{g}:E(M)\rightarrow\\{\text{green, black}\\}$, we associate every green
edge, say $e_{i}$, with a green $e_{i}$-diamond most of the time; but a green
$e_{i}$-triangle if $e_{i}$ is along an outer facet of $M$.

######  Definition 14.1.

Given $M$ with a green green tiling $T_{g}$, a _green diamond route_
$\mathbf{dr}_{g}$ in $M$ is a sequence
$\mathbf{dr}_{g}:=(e_{1},e_{2},\ldots,e_{k})$ of distinct green edges such
that every consecutive pair $e_{i}$\- and $e_{i+1}$-diamonds or triangles
share a common black edge.

######  Definition 14.2.

Continue from previous definition. We may consider
$\vec{\mathbf{dr}}_{g}:=(e_{1}\rightarrow e_{2}\rightarrow\ldots\rightarrow
e_{h})$ as a _directed_ green diamond route in $M$. In the directed mode, the
triangles involved in this particular route are separated into two classes:
_out-triangles_ and _in-triangles_.

For instance, in Figure 33 we have a 7-semi-MPG with a green tiling which
unfortunately has a green 5-cycle, namely
$C_{5}:=v_{5}$-$v_{6}$-$v_{7}$-$v_{c}$-$v_{a}$-$v_{5}$. The two graphs show
two different ways to demonstrate $(e_{1},e_{2},\ldots,e_{6})$ by marking
edges as sequence and $\vec{\mathbf{dr}}_{g}$ by a green-gray dashed line with
direction.

Figure 33. $\mathbf{dr}_{g}:=(e_{1},e_{2},\ldots,e_{6})$ and
$\vec{\mathbf{dr}}_{g}:=(e_{1}\rightarrow e_{2}\rightarrow\ldots\rightarrow
e_{6})$

On the second graph of Figure 33, we also indicate the two triangles of
$e_{1}$-diamond as the _initial-in_ (marked by “In”) and the _initial-out_
(marked by “Out”). And then there are some in-triangles (marked by “i”) and
out-triangles (marked by “o”) along the green-gray dashed line
$\vec{\mathbf{dr}}_{g}$. Actually we miss several “i” to mark, because if any
green triangle is marked by “o” then the triangle on the other side of the its
$e_{i}$-diamond must be the corresponding in-triangle.

It is nature to define a _green diamond ring_ in $M$. For instance, let us use
the first graph in Figure 33 again. We find that
$\mathbf{dr}_{g}:=(e_{2},e_{3},e_{4},e_{5},e_{6},e_{2})$ forms a green diamond
ring. Rings are good to switch the roles of in-triangles and out-triangles for
themselves.

###  14.1. Green diamond route vs green canal lines

In Section LABEL:RGB1-sec:Grandline we introduced canal lines with each them
along two parallel canal banks. At that time we mentioned that we shall treat
all triangle as nodes and came out the traditional idea about the dual graph
of $M$. Now let us formally define our _dual graph_ of $(M;T_{g})$ or
$(M;T_{rgb})$, denote by $DG(M;T_{g})$ or $DG(M;T_{rgb})$, which is a little
bit different from the traditional one.

Let us use Figure 34 to explain. The set of nodes $V(DG(M;T_{g})$ consists of
all triangle facets (circles) and some _pseudo nodes_ (rectangles) near-by and
along every outer facet. Notice that the traditional dual graph will set only
one node for every outer facet but we rather set $k$ pseudo nodes for a
$k$-gon outer facet. Every link of $DG(M;T_{g})$ crosses exactly an edge $e$
in $E(M)$, and we shall color every link according to the color of $e$ in
$T_{g}$. By the similar way, $DG(M;T_{rgb})$ can be defined.

Figure 34. vertices and edges in $(M;T_{g})$; nodes and links in $DG(M;T_{g})$

Given $DG(M;T_{g})$, a green canal line $gCL_{i}$ is a path going through
black links in $DG(M;T_{g})$. If $DG(M;T_{rgb})$ is provided, a green canal
line $gCL_{i}$ is a path going through red and blue links alternately. All
these $gCL_{i}$ are destined when $T_{g}$ or $T_{rgb}$ is given.

Given $DG(M;T_{g})$, a green diamond route $\mathbf{dr}_{g}$ or directed one
$\vec{\mathbf{dr}}_{g}$ is a path going through green and black links
alternately. If $DG(M;T_{rgb})$ is provided, all red and blue edges are
treated as black. These $\mathbf{dr}_{g}$ or $\vec{\mathbf{dr}}_{g}$ are
various for picking one of two black edges many times.

Although $DG(M;T_{g})$ is much clear to show diamond route and canal lines,
turning to this new graph it really is bothering us; so we keep using
$DG(M;T_{g})$ and $DG(M;T_{rgb})$.

###  14.2. Amending $T_{g}$ by a green diamond route or ring

In our study, there are two major ways to amending $T_{g}$ or $T_{rgb}$, and
if possible we wish to break up unwelcome green odd-cycles. The first way is
what we are going to introduce, and the second way is discussed in Section 16.
Let us see the following twp examples.

######  Example 14.3.

Let us adopt the 7-semi MPG $M$ and $T_{g}(M)$ in Figure 33 as the original
setting, and we are going to break the green odd-cycle
$C_{5}:=v_{5}$-$v_{6}$-$v_{7}$-$v_{c}$-$v_{a}$-$v_{5}$ in this original
$T_{g}(M)$. Applying edge-color-switch along
$\mathbf{dr}_{g}:=(e_{2},e_{3}\ldots,e_{6},e_{2})$, we get the first graph in
Figure 35. In addition, denote $e_{0}:=v_{3}v_{a}$, and $e_{-1}:=v_{5}v_{a}$.
Applying edge-color-switch along
$\mathbf{dr}^{\prime}_{g}:=(e_{1},e_{0},e_{-1},e_{1})$, we get the second
graph in Figure 35.

Figure 35. Eliminate a green odd-cycle

Let $e_{7}:=v_{5}v_{6}$. Applying edge-color-switch along
$\mathbf{dr}^{\prime\prime}_{g}:=(e_{0},e_{1},e_{2},\ldots,e_{7})$, we get the
first graph in Figure 36. Applying edge-color-switch along
$\mathbf{dr}^{\prime\prime\prime}_{g}:=(e_{4},e_{5},e_{6},e_{7})$, we get the
second graph in Figure 36.

Figure 36. Eliminate a green odd-cycle, more examples

All these four processes tear the green 5-cycle $C_{5}$ and create new odd-
cycle-free tilings in $M$. Since $M$ is One Piece, each of these four new
green tilings is grand and offers its own 4-coloring function.

######  Example 14.4.

We have a $(7,5)$-semi-MPG $M$ in Figure 37 and an original G-tiling
$T_{g}(M)$ as the first graph. We also see a green odd-cycle $C_{7}$ in
$T_{g}(M)$. This green odd-cycle is along the annular shape of $M$. After the
first edge-color-switch process along the the green-gray dashed line
$\mathbf{dr}_{g}$, we obtain the middle graph with a new green tiling
$T^{\prime}_{g}$. Unfortunately $T^{\prime}_{g}$ is not grand.

Figure 37. Eliminate a green odd-cycle; the middle is not grand

Keep going! Let us apply the second edge-color-switch process along the the
green-gray dashed line $\mathbf{dr}^{\prime}_{g}$, and then obtain
$T^{\prime}_{g}$ as the third graph. Finally we achieve a grand G-tiling∗ (the
abbreviation of “G-tiling without any green odd-cycle”).

######  Remark 14.5.

By the first example, we experience a constructing method to transform a
normal green tiling with odd-cycles into a G-tiling∗. However, this
constructing method does not guarantee an odd-cycle-free result, because some
other new green odd-cycles might be created after this edge-color-switch
process. By the second example, we experience that the grand property might be
destroyed. To avoid this awkward situation, we shall choose a green diamond
route that crosses the green odd-cycle in and out. Fortunately, most of time
we deal with One Piece; thus any green diamond route must be in-and-out w.r.t.
every green odd-cycle.

##  15\. Orientation by an initiator

In the previous section, particularly in the second graph of Figure 33, we
introduced the _initial-in-triangle_ (marked by “In”) and the _initial-out-
triangle_ (marked by “Out”); and then we indicate _in-triangles_ (marked by
“i”) and _out-triangles_ (marked by “o”) along a given directed green diamond
route $\vec{\mathbf{dr}}_{g}:=(e_{I}=e_{0}\rightarrow
e_{1}\rightarrow\ldots\rightarrow e_{k})$. Usually, we need only mark all out-
triangles by “o” and ignore “i”.

The initial-in-triangle and initial-out-triangle form the _initial-
$eI$-diamond_. However, only an initial-$eI$-diamond can have two possible
directions by switching $\triangle\text{In}$ and $\triangle\text{Out}$. Thus,
as for Figure 33 we had $eI=e_{1}$ and we shall denote
$\triangle\text{Out}:=(eI,v_{b})_{\text{O}}$ as the initial-out-triangle
(sometimes we just use Out without a $\triangle$ in from of it), and
$\triangle\text{In}:=(eI,v_{2})_{\text{I}}$ as the initial-in-triangle. Once
we assign an initial-in-triangle or an initial-out-triangle, we can generate
many different green diamond routes and each directed green diamond route
$\vec{\mathbf{dr}}_{g}$ offers its class of out-triangles and in-triangles.

######  Example 15.1.

Let us adopt the right graph in Figure 33 first, but remove the original
directed green diamond route on that graph. In Figure fig:inoutTriangles, we
build another two routes starting at $(eI,v_{b})_{\text{O}}$. By these two
directed green diamond routes together with the route given in the right graph
in Figure 33, we obtain 10 out-triangles in total that are shown by the right
graph in Figure 38.

Figure 38. $OT(e_{I},v_{b})_{\text{O}}=\\{\text{out-triangles generated by
$(eI,v_{b})_{\text{O}}$}\\}$

Most of in-triangles lay on the opposite side of out-triangles with their
corresponding green edges in middle. Some exceptional in-triangles happen, for
instance, $\triangle v_{5}v_{6}v_{b}$ is an in-triangle without its
corresponding out-triangle. Obviously, these exceptional in-triangles only
happen when a green edge lay on the outer facet of $M$. One more interesting
observation: there are two out-triangles $\triangle v_{a}v_{2}v_{3}$ and
$\triangle v_{c}v_{2}v_{8}$ “ _adjacent to_ ” the initial-in-triangle
$(e_{I},v_{2})_{\text{I}}$. This means in $T_{g}$ at least two green diamond
rings passing through $e_{I}$. Since $e_{I}$ lays on the green 5-cycle
$C_{5}=v_{a}$-$v_{c}$-$v_{7}$-$v_{6}$-$v_{5}$-$v_{a}$, we now have at least
two edge-color-switch processes to break $C_{5}$.

With the help of Example 15.1, we experience the _orientation_ of triangles
generated by a fixed initial-out-triangle $\triangle\text{Out}$. Given an MPG
or semi-MPG $M$ with a green tiling $T_{g}(M)$, let us choose an particular
green edge $eI$ and one of its associating triangle $(eI,u)$ to be the
_initial-out-triangle_ $\text{Out}:=(e,u)_{\text{O}}$), and in the same time
_initial-in-triangle_ $\triangle\text{In}:=(e,v)_{\text{I}}$ is chosen unless
$e$ is along a outer facet of $M$. A $e$-diamond or $e$-triangle is
_reachable_ if there is a directed green diamond routes
$\vec{\mathbf{dr}}_{g}=(e_{I}=e_{1}\rightarrow
e_{2}\rightarrow\ldots\rightarrow e_{k}=e)$ for some $k\geq 1$ and all $e_{i}$
distinct. If $e$ is not along a outer facet of $M$, at the final two steps of
$\vec{\mathbf{dr}}_{g}$ as we reaching $e$, we see an in-triangle (i) first
and then an out-triangle (o). Particularly when $k=1$ and the length of
$\vec{\mathbf{dr}}$ is zero that means $(eI,v)$ and $(eI,u)$ are the only
reachable in- and out-triangles respectively by this $\vec{\mathbf{dr}}$. Let
denote the sets

$\displaystyle IT(eI,u)_{\text{O}}$ $\displaystyle:=$
$\displaystyle\\{\text{in-triangles generated by $(eI,u)_{\text{O}}$,
including $\triangle\text{In}$}\\};$ $\displaystyle OT(eI,u)_{\text{O}}$
$\displaystyle:=$ $\displaystyle\\{\text{out-triangles generated by
$(eI,u)_{\text{O}}$, including $\triangle\text{Out}$}\\}.$

Let $Tri(M)$ consists of all triangles of $M$. We denote the following three
disjoint subsets of $Tri(M)$:

$\displaystyle BiT(eI,u)_{\text{O}}=\\{\text{bi-oriented}\\}$
$\displaystyle:=$ $\displaystyle OT(eI,u)_{\text{O}}\cap IT(eI,u)_{\text{O}};$
$\displaystyle NonT(eI,u)_{\text{O}}=\\{\text{non-oriented}\\}$
$\displaystyle:=$ $\displaystyle Tri(M)-(OT(eI,u)_{\text{O}}\cup
IT(eI,u)_{\text{O}});$ $\displaystyle UniT(eI,u)_{\text{O}}=\\{\text{uni-
oriented}\\}$ $\displaystyle:=$ $\displaystyle
Tri(M)-BiT(eI,u)_{\text{O}}-NonT(eI,u)_{\text{O}}.$

In other worlds, a _non-oriented_ triangle or diamond is never reachable by
any $\vec{\mathbf{dr}}_{g}$; a _bi-oriented_ triangle or diamond can be
reachable from two different directions.

######  Example 15.2.

Let us still use the right graph in Figure 38 with
$\triangle\text{Out}=(eI,v_{b})_{\text{O}}$ in Example 15.1. We have
$BiT(eI,u)_{\text{O}}=\\{\text{triangles inside
$v_{0}$-$v_{1}$-$v_{2}$-$v_{c}$-$v_{8}$-$v_{7}$-$v_{0}$}\\}$ and
$NonT(eI,u)_{\text{O}}=\emptyset$. We shade the region of this
$BiT(eI,u)_{\text{O}}$ by gray. Now we show another two examples in Figure 39.
On the first graph, we assign
$\triangle\text{Out}:=(eI^{\prime},v_{4})_{\text{O}}$.

Figure 39. $BiT$ in gray

We demonstrate three directed green diamond routs to determine that
$BiT(eI^{\prime},v_{4})_{\text{O}}=\\{\text{triangles inside
$v_{0}$-$v_{7}$-$v_{8}$-$v_{c}$-$v_{b}$-$v_{6}$-$v_{0}$}\\}$ and
$NonT(eI^{\prime},v_{4})_{\text{O}}=\emptyset$. We can see the gray area for
$BiT(eI^{\prime},v_{4})_{\text{O}}$ in the second graph. The third graph is
interesting, where we assign
$\triangle\text{Out}=(eI^{\prime\prime},v_{b})_{\text{O}}$ and we find that
$OT((eI^{\prime\prime},v_{b})_{\text{O}})=Tri(M)$. That means starting at
$(eI^{\prime\prime},v_{b})_{\text{O}}$ and there is a $\vec{\mathbf{dr}}_{g}$
reaching any triangle as an out-triangle. In this way,
$BiT(eI^{\prime},v_{4})_{\text{O}}=Tri(M)-\\{(eI^{\prime\prime},v_{b})\\}$,
i.e., almost all triangles are bi-oriented. There is a hidden meaning: Suppose
$M$ is a subgraph of $\hat{M}$ and suppose a green diamond route from outside
of $M$ enters through the gate $eI^{\prime\prime}$. Since all triangles in
$Tri(M)$ are bi-oriented except $(eI^{\prime\prime},v_{b})$. Say $\triangle
v_{i}v_{j}v_{k}$ is bi-oriented and $v_{i}v_{j}$ is along the outer facet of
$M$. We can build an extended $\vec{\mathbf{dr}}_{g}$ that goes out through
the gate $v_{i}v_{j}$ and then back into $\hat{M}-M$. Back to the first graph.
If the gate $v_{2}v_{3}$ is the entrance, then a possible exit can be any of
$v_{3}v_{4}$, $v_{5}v_{6}$, $v_{6}v_{0}$ and $v_{0}v_{1}$, where $v_{1}v_{2}$
and $v_{4}v_{5}$ are impossible.

###  15.1. Constructing RGB-tilings or G-tilings by diamond routes

By our method, to prove the Four Color Theorem we start with the false
assumption $EP\in e\mathcal{MPGN}4\neq\emptyset$, and then use the follow-up
property $EP-\\{e\\}$ is 4-colorable rather than use $EP-\\{v\\}$ is
4-colorable with particularly $\deg(v)=5)$. A 4-colorable $EP-\\{e\\}$ means
the existence of RGB-tilings on $EP-\\{e\\}$, and the existence of G-tilings
on $EP$ each of which is almost a G-tiling∗ but a green odd-cycle passing
through $e$.

The truth of the Four Color Theorem for all planar graphs guarantees that all
MPG’s have their own RGB-tilings. However, without using the Four Color
Theorem, it is independent problem that all MPG’s have their own RGB-tilings.

Besides the existence property of RGB-tilings or G-tilings, constructing
methods are also interesting. We try to build a green tiling on an MPG or an
an $(n_{1},n_{2},\ldots,n_{k})$-semi-MPG from initially no green edges at all.
The author have achieved several results on this constructing method to build
a green tiling on $M$ by using $OT(e,u)_{\text{O}}$ . The results will be
collected in another paper in the near future.

##  16\. Generalized canal lines and Kempe chains

We are now introducing the second topic of this article– _generalized canal
lines_. The study is pretty long and we just use a pentagon in $EP$ to
demonstrate the idea in this section.

The reader shall see the previous Sections LABEL:RGB2-sec:tanglingProperty and
LABEL:RGB2-sec:ediamond to review normal _canal lines_. Basically, given an
MPG or $(n_{1},n_{2},\ldots,n_{k})$-semi-MPG $M$, a _grand_ R-tiling and red
grand canal system are same idea of two representations (See Lemma
LABEL:RGB1-thm:grandRtilingGrandLineSys). First of all, we need an R-tiling
$T_{r}:E(M)\rightarrow\\{\text{red, black}\\}$. The following is a brief
review of a _grand_ R-tiling and a _grand_ R-canal system.

  * •

A grand R-tiling: It is _grand_ one if the vertex set $V(M)$ can be
partitioned into two disjoint parts $V_{1}$ and $V_{2}$ such that the subgraph
$G_{bl}$ of $M$ induced by all black edges is a bipartite graph on bipartite-
sets $V_{1}$ and $V_{2}$, and also there is no red edge between $V_{1}$ and
$V_{2}$. (Most of time, we will draw red edges in $V_{1}$ thicker than
$V_{2}$.)

  * •

A grand R-canal system: It is _grand_ one if we can arrange orientation for
all R-canal lines such that the flow directions are parallel but opposite on
the two sides of each red edge.

When an RGB-tiling is provided, a _normal_ red canal line is also
simultaneously a G-diamond route and a B-diamond route that follows the
orientation of R-canal system, i.e., follows the two sides of red river banks.
R/G/B are actually symmetric and switchable under some circumstances. In the
previous sections we used G-diamond routes and here we introduce R-canal
lines, because a green light in traffic means Go and free to cross; a red
light in traffic means STOP and no crossing. However, a green diamond route in
a provided RGB-tiling is not necessary a red canal line. Between any two
consecutive green edges along a green diamond route, it could be a red edge or
a blue one.

A _generalized canal line or ring_ mainly follows the orientation of
R-/G-canal system but crosses some particular red/green edges occasionally. In
the following, we will use several example to explain how to operate a
generalized canal line or ring.

Please, refer to some figures in Section LABEL:RGB1-sec:RGB4coloring for
examples and counterexamples. Briefly we use “R-tiling∗” to stand for the
abbreviation of “R-tiling without any red odd-cycle.” Notice that a grand
R-tiling is not necessary an R-tiling∗. The study of the rest paper highly
depends on Sections LABEL:RGB1-sec:RGB4coloring, LABEL:RGB1-sec:Grandline,
LABEL:RGB2-sec:tanglingProperty and LABEL:RGB2-sec:NecSufConds.

######  Lemma 16.1.

Let $M$ be an MPG or an $n$-/$(n_{1},n_{2},\ldots,n_{k})$-semi-MPG with an
R-tiling $T_{r}$.

  1. (a)

A red tiling $T_{r}:=\bigcup_{i}rC_{i}$ on $M$ and a red canal system
$rCLS:=\bigcup_{j}rCL_{j}$ are different perspectives of looking the same
thing.

  2. (b)

By linking nodes of triangles, a red canal line $rCL_{j}$ of $T_{r}$ is either
(b1) a close cycle, called _canal ring_ , or (b2) a path starting from one
outer facet and ending at another outer facet (maybe the same outer facet),
while the pair of entrance and exit on the two end of this path are both black
edges along the outer facets.

  3. (c)

If $M$ is an MPG, then every red canal line $rCL_{j}$ is ring. If $M$ is an
$n$-semi-MPG, then the connection of entrances and exits of this red canal
system $rCLS$ creates a non-crossing match among all black edges along the
unique outer facet.

###  16.1. The rotation of the dual Kempe chains w.r.t. $(EP,v)$ with
$\deg(v)=5$

To prove Four Color Theorem, approaching by contrapositive method is nearly
inevitable. We shall assume $e\mathcal{MPGN}4$ nonempty and deal with a pseudo
extremum graph, say $EP$, which is minimum in cardinality among all
non-4-colorable MPG’s. The classical Kempe’s proof consider a 5-semi-MPG
defined by $P:=EP-\\{v\\}$, where $v$ is any vertex in $EP$ with $\deg(v)=5$.
Our approach simulate Kempe’s classical proof: Given the same situation as the
setting of Kempe’s proof, we consider a 4-semi-MPG $Q_{i}:=EP-\\{vv_{i}\\}$
for the five neighbors $v_{1},v_{2},\ldots,v_{5}$ of $v$. By Theorem
LABEL:RGB1-thm:eMPG4, any non-trivial subgraph of $EP$ is 4-colorable; so $P$
and $Q_{i}$ are all 4-colorable.

The classical Kempe’s proof applies vertex-color-switching, and our renewal
method uses edge-color-switching. Please, refer to Sections
LABEL:RGB2-sec:RGBKempeChainDeg5, LABEL:RGB2-sec:tanglingProperty,
LABEL:RGB2-sec:ediamond and LABEL:RGB2-sec:NecSufConds for details.

Let us introduce the first main idea involved generalized canal rings: _the
rotation of the dual Kempe chains_ w.r.t. $(EP,v)$. The idea is demonstrated
by Figure 40 briefly. Given any extremum planar graph $EP\in
e\mathcal{MPGN}4$, there are at least 12 vertices of degree 5 (see Theorem
LABEL:RGB1-thm:V5, and also in [1]). Let $v\in V(EP)$ with $\deg(v)=5$ and
$v_{1},\ldots,v_{5}$ be its five neighbors. Let us denote
$\Omega:=v_{1}$-$v_{2}$-$\ldots$-$v_{5}$-$v_{1}$, and $\Sigma$
($\Sigma^{\prime}$) to be the sub-area or sub-graph of $EP$ inside (outside)
of $\Omega$.

We will prove that all six graphs in Figure 40 with their own RGB-tiling on
$EP-\\{vv_{i}\\}$ for $i=1,\ldots,5$ in Figure 40 are different statuses of a
same congruence class. Please, refer to Subsection LABEL:RGB2-sec:SynEquivCong
for the definition of the three different equivalence relations: synonym
($\overset{\text{\tiny syn}}{=}$, $\langle\cdot\rangle$), equivalence
($\equiv$, $[\cdot]$ under $\Omega$) and congruence ($\cong$ under $\Omega$).

Figure 40. The rotation of the dual Kempe chains w.r.t. $(EP;v)$

Here we focus on the this _pentagon sub-area_ of $EP$ (every $EP$ without
exception), it is nature to name this picture of $(EP;v)$ with $\deg(v)=5$ by
$T^{5}$ particularly. Let $\Omega:=v_{1}$-$v_{2}$-$\ldots$-$v_{5}$-$v_{1}$ and
$\Sigma$ ($\Sigma^{\prime}$) is the subgraph of $EP$ inside (outside)
$\Omega$. Due to the shape of pentagon sub-area, we also denote $Ptg:=\Sigma$
or simply use “$5$” as a superscript for short, where $\Sigma$ is a general
notation for all kinds of sub-area. We start with an RGB-tiling (as same as a
4-coloring function) on $Q_{1}:=EP-\\{vv_{1}\\}$; this RGB-tiling, denoted by
$T^{5}(Q_{1})$, is guaranteed by Theorem LABEL:RGB1-thm:eMPG4: any non-trivial
subgraph of $EP$ is 4-colorable. Moreover, we use $\langle
T^{5}(Q_{1})\rangle$ to denote the class of synonyms of $T^{5}(Q_{1})$ which
consist of six RGB-tilings on $Q_{1}:=EP-\\{vv_{1}\\}$ by switching
(permuting) edge-colors red, green and blue all over whole $Q_{1}$. We will
use the equivalence class $[T^{5}(Q_{1})]$ for this kind of process later as a
comparison.

Figure 41. Type A and Type B RGB-tilings for $EP-\\{e\\}$

Two more things need to mention: (1) Most of time we use Type A $e$-diamond
for the rest of this study; (2) $T^{5}(Q_{1})$ is just one of many different
RGB-tiling on $Q_{1}$ and and $\langle T^{5}(Q_{1})\rangle$ is just one of
many different classes of synonyms. For the reader’s convenience, we re-draw
Type A and Type B $e$-diamonds in Figure 41.

Before we start our process, let us look at (a) to (f) in Figure 40
individually. So far these six Type A RGB-tilings $T(Q_{i})$ are independent
and their existence dues to Theorem LABEL:RGB2-thm:EPediamond due to a fixed
$e$-diamond.

######  Remark 16.2.

Because the pentagon $\Sigma$ is very simple, the equivalence class
$[T(Q_{i})]$ is unique and it has the dual Kempe chains $(K_{r},K_{g})$ w.r.t.
$(EP;vv_{i})$ as the skeleton in $\Sigma^{\prime}$; however $\langle
T(Q_{i})\rangle$ might have many different classes of six synonyms for a fix
$i$. According to the pictures only, we see that (a) and (f) are equivalent,
even though we just see red and green edge-colors switched. But we can not
guarantee that the two underline RGB-tilings of (a) and (f) are synonyms,
because the same _skeleton_ in $\Sigma^{\prime}$ shared by both (a) and (f)
might has different pair of paths. Two synonyms must share same paths of
skeleton in $\Sigma^{\prime}$. In this pentagon sub-area or $\Omega$, the
skeleton in $\Sigma^{\prime}$ can only be the dual Kempe chains
$(K_{r},K_{g})$.

Starting with (a):$\langle T^{5}(Q_{1})\rangle$ in Figure 40 where we draw a
_red generalized canal ring_ , denoted by $rGCL_{1}$, shown as a red dashed
line. (Both red canal ring and canal line are always denoted by $rCL_{i}$ and
never by $rCR_{i}$.) It is generalized because it crosses the red edge
$vv_{3}$ and also it crosses the yellow double-line111This double-line is
actually orange color because yellow color in not easy to see for
publications. $vv_{1}$. Now let us perform edge-color-switching (ECS for
short222We use acronyms VCS and ECS to stand for “vertex-color-switching” and
“edge-color-switching” respectively.) on $rGCL(v_{1}v_{2})$ and then we obtain
(b) in Figure 40. Because the new RGB-tiling $\langle T^{5}(Q_{2})\rangle$ is
obtain by perform ECS on red canal ring, we also write it as $\langle
T^{5}(Q_{1})\rangle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+1}$.

So, how to perform edge-color-switching on (or along) a red generalized canal
ring? It is very simple:

  * •

Switch edge colors of green and blue, just like what we do for a normal red
canal line;

  * •

Switch edge colors of red and yellow double-line, and this switching rule is
what we perform for the “generalized” segment.

  * •

To perform edge-color-switching on (or along) a green/blue generalized canal
ring, we just apply the two items above, under symmetry of three colors.

In total, we perform ECS five times in Figure 40 and alternately using
red/green generalized canal rings. We use different ways to remark these six
graphs. For instance, (e) is actually $\langle T^{5}(Q_{5})\rangle$; however
when we follow the previous four processes, $\langle
T^{5}(Q_{1})\rangle+4_{rgrg}$ is a good way to represent this equivalence
class.

######  Remark 16.3.

After explore these five processes and the remarks labeled for (a) to (f), we
find that the class $[T^{5}(Q_{i})]$ is much better than the class $\langle
T^{5}(Q_{i})\rangle$. We will use former one in the rest of the paper.

######  Remark 16.4.

If we start with (f) and perform ECS five more times, then we can get a new
$[T^{5}(Q_{1})]$, even though this new $[T^{5}(Q_{1})]$ might have different
underline RGB-tiling compared with the original (a): $T^{5}(Q_{1})$, i.e., we
have two RGB-tilings of a same equivalence class but not necessary the same.

By definition of congruence relation defined in Subsection
LABEL:RGB2-sec:SynEquivCong, we have

$[T^{5}(Q_{1})]_{\Omega}\cong[T^{5}(Q_{2})]_{\Omega}\cong\cdots\cong[T^{5}(Q_{5})]_{\Omega}.$

where the subscript $\Omega$ means the sub-area that $[\cdot]$ builds up.
Therefore, we have the following theorem.

######  Theorem 16.5.

Let $EP\in e\mathcal{MPGN}4$, $v\in V(EP)$ with $\deg(v)=5$ where the five
neighbors of $v$ form $\Omega:=v_{1}$-$v_{2}$-$\ldots$-$v_{5}$-$v_{1}$. Under
the equivalence relation $[\cdot]_{\Omega}$, all RGB-tilings on $EP$ are in a
same congruence class.

Be careful! Once we focus on another topic for discussion as well as different
$\Omega^{\prime}$, then another equivalence relation
$[\cdot]_{\Omega^{\prime}}$ presents; so this theorem does not necessarily
hold.

######  Remark 16.6.

There is another reason that we had better use $[\cdot]$, rather than
$\langle\cdot\rangle$. Again, let us focus on (a) which is both in Figures 40
and 42. This time we apply the other red generalized canal ring drawn as the
red dashed line in Figures 42. Yes, there are only two _major_ 333Only _major_
red generalized canal rings (by our method) or _major_ red-connected
components (by Kempe’s method) can effect the skeleton in $\Sigma^{\prime}$.
Please, see Section LABEL:RGB2-sec:tanglingProperty for details. red
generalized canal rings to reach a Type A $vv_{2}$-diamond shown as (b) and
(b’) in the two figures. Visually it is clear that (b) and (b’) just a same
graph with green/blue switched. However, (b) and (b’) are not necessary same
class of synonyms, but we are sure that (b) and (b’) have same skeleton in
$\Sigma^{\prime}$; therefore the graphs of (b) and (b’) are equivalent. One
more thing shall be kept in mind: $K_{r}|_{v_{1}}^{v_{3}}$ represents a red-
connected component connecting $v_{1}$ and $v_{3}$ that means
$K_{r}|_{v_{1}}^{v_{3}}$ might contain a bunch of red paths from $v_{1}$ to
$v_{3}$. Any red canal ring inside $K_{r}|_{v_{1}}^{v_{3}}$ is not _major_.
Also notice that

$[T^{5}(Q_{1}){\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+1}]:=[\langle
T^{5}(Q_{1})\rangle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+1}]$

and the left-hand-side is our standard notation.

Figure 42. The other major red generalized canal ring for (a)

######  Definition 16.7.

The two major red generalized canal rings shown in the the first graph in
Figures 40 and in 42 are usually denote by $rGCL(v_{1}v_{2})$ and
$rGCL(v_{1}v5)$, because they come out of $\Sigma$ from edges $v_{1}v_{2}$ and
$v_{1}v5$ respectively. We say $rGCL(v_{1}v_{2})$ and $rGCL(v_{1}v5)$ are
_conjugate_ for the results, (b) and (b’), of ECS on each of them are
equivalent. If there are three or more _major_ red generalized canal rings,
the idea of _conjugation_ is more complicate. We will talk about it then.

###  16.2. More concepts about $Ptg$

There are still two concepts to explore $Ptg$. The first one is a 4-colorable
function on $Ptg$ locally or this $Ptg$ is a sub-area of a 4-colorable MPG.
The only possible representative is shown as the first graph in Figure 43. One
of its features is the setting of the four red edges.

Figure 43. 4-colorable locally and a yellow double-line on $\Omega$

The second concept comes from a half $e$-diamond of Type A in $Ptg$ shown as
the rest three graphs in Figure 43.

######  Lemma 16.8.

If $EP$ has $Co_{\alpha}(Ptg)$, then $\deg(v_{2},v_{3})\geq 6$.

###### Proof.

If $\deg(v_{2})=5$ (or $deg(v_{3})=5$) then this vertex has to follow the
tangling property w.r.t. a degree 5 vertex in $EP$. However,
$K_{r}|_{v_{2}}^{v_{3}}$ is too simple to interest with $K_{g}$. Thus,
$\deg(v_{2})\neq 5$. Please, see Lemma LABEL:RGB2-thm:deg5tangling. ∎

Figure 44. Good $Co_{\beta}(Ptg)$/$Co_{\gamma}(Ptg)$, and 4-colorable ones

######  Corollary 16.9.

If $EP$ has $Co_{\beta}(Ptg)$ with $\deg(v_{2})=5$ or $\deg(v_{3})=5$, then
$K_{b}|_{v_{2}}^{v_{5}}$ is impossible and $K_{b}|_{v_{1}}^{v_{4}}$ must
exist. Please, refer to Figure 44.

######  Corollary 16.10.

If $EP$ has $Co_{\gamma}(Ptg)$ with $\deg(v_{2})=5$ or $\deg(v_{3})=5$, then
$K_{g}|_{v_{1}}^{v_{4}}$ is impossible and $K_{g}|_{v_{2}}^{v_{5}}$ must
exist. Please, refer to Figure 44.

##  17\. Kempe chains around two adjacent vertices of degree 5 in $EP$

Given a particular $EP\in e\mathcal{MPGN}4$ who has two adjacent vertices, say
$a$ and $b$, of degree 5, us will perform ECS on generalized canal ring around
$a$ and $b$ to obtain many Kempe chains in different statuses.

Let $T\\!D:=(\\{a,b\\};\deg(a,b)=5)$. It is the _topic for discussion_. Around
$T\\!D$ is the _boarder_ $\Phi$ as a cycle. Here we have
$\Phi:=v_{1}$-$v_{2}$-$c$-$v_{4}$-$v_{5}$-$d$-$v_{1}$.444Here we use $\Phi$ to
distinguish from $\Omega$ in Subsection 16.1. The formation definition of
$T\\!D$ will be given in Subsection 18.1. Because $\deg(a,b)=5$, we also use
“$55$” to stand this particular $EP$. The two graphs in Figure 45 are the
initial RGB-tilings of $EP$ with Type A $ab$-diamond under equivalence. The
subscripts $\alpha$ and $\beta$ are just labels to distinguish them. Clearly,
$[T_{\alpha}^{55}]\not\equiv[T_{\beta}^{55}]$. We will show that
$[T_{\alpha}^{55}]\cong[T_{\beta}^{55}]$. Another obvious observation is that
the equivalence class $[T_{\alpha}^{55}]$ of RGB-tilings is symmetric w.r.t.
the vertical line and the horizontal one; so is the class $[T_{\beta}^{55}]$
with more imagination.

Figure 45. The two initial RGB-tilings of $EP$ with $T\\!D=55$

For $[T_{\alpha}^{55}]$ there are two major red (green) generalized canal
rings, namely $rGCL(dv_{1})$ and $rGCL(v_{1}v_{2})$ ($gGCL(cv_{2})$ and
$gGCL(v_{1}v_{2})$). For $[T_{\beta}^{55}]$ there are two major red (green)
generalized canal rings, namely $rGCL(v_{1}v_{2})$ and $rGCL(cv_{2})$
($gGCL(v_{1}v_{2})$ and $gGCL(dv_{1})$). Of course, all of them are conjugate
in pairs.

###  17.1. Let us rock-n-roll

Starting with the initial status $S_{0}:=[T_{\alpha}^{55}]$, let us perform 10
consecutive processes of ECS according to those red/green dashed lines drawn
in Figure 46. The whole figure shows the rotation of many Kempe chains around
vertex $a$ and $b$, or around $\Phi$.

Figure 46. Rock-n-roll around $(\\{a,b\\};\deg(a,b)=5)$

######  Remark 17.1.

Some details in Figure 46 need to mention. We have two versions of
$rGCL(dv_{1})$, where we do show the one that turns around vertex $a$, and the
other one that turns around vertex $b$. That is why we have both
$K_{g}|_{c}^{v_{1}}$ and $K_{g}|_{c}^{v_{5}}$ in $S_{1}$. Also notice that
even though the graph we draw for $S_{1}$ seems to have $\mathrm{Gdeg}(c)=3$,
but it is more possible that $\mathrm{Gdeg}(c)=2$ for $K_{g}|_{c}^{v_{1}}$ and
$K_{g}|_{c}^{v_{5}}$ sharing one green edge in $\Sigma^{\prime}$. So far we
still have $\deg(c)\geq 5$.

######  Remark 17.2.

The Kempe chain $K_{r}|_{d}^{v_{4}}$ in $S_{2}$ and $S_{3}$ can be replaced by
$K_{r}|_{d}^{c}$, because we can only guarantee that red edge $cv_{4}$ is red
connected with $d$. If it is really $K_{r}|_{d}^{c}$, then $\deg(c)\geq 6$.
The same thing happens in $S_{3}$ and $S_{4}$ for $K_{g}|_{v_{2}}^{v_{4}}$; it
can be either replace by $K_{g}|_{v_{2}}^{v_{5}}$ or $K_{g}|_{v_{2}}^{d}$. If
it is really $K_{g}|_{v_{2}}^{v_{5}}$, then $\deg(v_{5})\geq 7$. If it is
really $K_{g}|_{v_{2}}^{d}$, then $\deg(d)\geq 6$. There are more discussion
by this similar idea, and we will talk about it then.

######  Remark 17.3.

The notation $|S_{4}$ in the third line of this figure means reflection of
$S_{4}$ w.r.t. the vertical line. There is also notation
$\underline{S_{\ast}}$ that means reflection of $S_{\ast}$ w.r.t. the
horizontal line.

######  Remark 17.4.

For $S_{1}$ there are three major green generalized canal rings, namely
$gGCL(v_{1}v_{2})$ (the given green dashed line in this figure)
$gGCL(v_{4}v_{5})$ and $gGCL(dv_{1})$. So, what is the idea of _conjugation_
now? The reader can check that ECS on $gGCL(v_{1}v_{2})$ is conjugate with
$gGCL(v_{4}v_{5})\oplus gGCL(dv_{1})$, where $\oplus$ means combination or
connecting these two generalized canal line in a proper way; also
$gGCL(v_{4}v_{5})$ is conjugate with $gGCL(v_{1}v_{2})\oplus gGCL(dv_{1})$. We
could choose ECS on $gGCL(v_{4}v_{5})$ as our second process to change $S_{1}$
and then obtain $S^{\prime}_{2}$. Clearly, $S^{\prime}_{2}\equiv|S_{2}$; so
the rest after $S^{\prime}_{2}$ are all reflections w.r.t. the horizontal
line. Even though $gGCL(dv_{1})$ is conjugate with $gGCL(v_{1}v_{2})\oplus
gGCL(v_{4}v_{5})$, it seems useless; because applying ECS on $gGCL(dv_{1})$
does not make a single $e$-diamond of Type A but two of Type B. Please, see
Figure 47 and refer to the next remark.

According to Figure 46, we have

(17.1)
$[S_{0}=T_{\alpha}^{55}]_{\Phi}\cong[S_{1}]_{\Phi}\cong\cdots\cong[S_{5}=T_{\beta}^{55}]_{\Phi}\cong\cdots\cong[S_{10}]_{\Phi}\equiv[T_{\alpha}^{55}]_{\Phi}.$

######  Remark 17.5.

Since $S_{8}\equiv|S_{2}$ and $S_{9}\equiv S_{1}$, something happens in
between $S_{1}$ and $S_{2}$, as well as in between $S_{8}$ and $S_{9}$, are
similar. In the last remark, we said that performing ECS on $gGCL(dv_{1})$ in
$S_{1}$ seems useless. Let us try it, as well as performing ECS on
$rGCL(v_{1}v_{2})$ in $S_{8}$. We obtain $S_{x}\cong S_{y}$ and they have two
Kempe chains of only one color. Notice that the pair of yellow double-lines in
$S_{x}$ are different from the ones in $S_{y}$. However, the congruence of
them is decided by the edge-coloring along $\Phi$, denoted by $Co(\Phi)$, and
the skeleton in $\Sigma^{\prime}$. The difference inside $\Sigma$ between
$S_{x}$ and $S_{y}$ associates with $\Sigma$-adjustment that will be
introduced later. Now we can explore this interesting $S_{x}$.

Figure 47. About $S_{1}$ and $S_{8}$

According to Figure 47 , we have

(17.2)
$[S_{0}=T_{\alpha}^{55}]_{\Phi}\cong[S_{x}]_{\Phi}\equiv[S_{y}]_{\Phi}.$

We use notation $|S_{\ast}$ and $\underline{S_{\ast}}$ to denote the
reflection images of $S_{\ast}$ w.r.t. the vertical line and the horizontal
one respectively. Also $|\underline{S_{\ast}}$ is reflected twice. Let
$[S_{\ast}]_{\text{sym}}$ consists of the equivalence of the these four
reflection images of $S_{\ast}$. Most of time $[S_{\ast}]_{\text{sym}}$ has
four different elements, but both $[T_{\alpha}^{55}]_{\text{sym}}$ and
$[T_{\beta}^{55}]_{\text{sym}}$ have only one element. Due to this fact of
only one element and Equations 17.1 and 17.2, we derive the next lemma.

######  Lemma 17.6.

All elements in $\\{[S_{0}],[S_{1}],\ldots,[S_{9}],[S_{x}]\\}_{\text{sym}}$,
where the subscript sym means this set consists all symmetric images w.r.t.
the vertical line and the horizontal one, are congruent to each other.

Here is one more amazing and important property.

######  Theorem 17.7.

Let $EP\in e\mathcal{MPGN}4$ with $T\\!D:=(\\{a,b\\};\deg(a,b)=5)$ and it is
drawn as the underlining graph shown in Figure 45. Also we adopt the notation
$\Phi$, $\Sigma$ and $\Sigma^{\prime}$. Let us fix the subgraph
$\Sigma^{\prime}$ and consider all kinds of MPG’s, denoted by $M_{\ast}$, such
that $M_{\ast}$ has exactly two vertices inside $\Phi$. Among all these
$M_{\ast}$, only $EP$ is non-4-colorable.

###### Proof.

We sill name the two vertices inside $\Phi$ by $a$ and $b$. The first MPG that
we consider is $M_{1}$ show as the first (underlining) graph in Figure 48. By
the existence of RGB-tiling $S_{x}$ in $\Sigma^{\prime}$ and the setting of

Figure 48. $M_{1}$, $M_{2}$ and the rest of 4-colorable $M_{\ast}$

edge-coloring inside $\Phi$, we prove that $M_{1}$ is 4-colorable. Notice that
the green cycle in $M_{1}$ is even, and even if the possible blue dashed
$K_{b}|_{c}^{d}$ exists we see a blue even-cycle. The second graph in Figure
48 MPG $M_{2}$ is the reflection of $M_{1}$ w.r.t. the vertical line. Clearly
$M_{2}$ is 4-colorable.

Among all MPG’s $M_{\ast}$, including some graphs might have edges linking
vertices in $\\{c,d,v_{1},v_{2},v_{4},v_{5}\\}$ (for example, given edge
$v_{1}v_{4}$), only $EP$, $M_{1}$ and $M_{2}$ can keep $\deg(a,b)=5$; the rest
MPG’s of $M_{\ast}$ must have $\deg(a)\leq 4$ or $\deg(b)\leq 4$. Since
$|M_{\ast}|=\omega$, which is the same order of all extremum planar graphs in
$e\mathcal{MPGN}4$, the rest MPG’s of $M_{\ast}$ must be 4-colorable by
Corollary LABEL:RGB1-thm:V5more2. The proof is complete. ∎

######  Lemma 17.8.

Let $EP\in e\mathcal{MPGN}4$ with $T\\!D:=(\\{a,b\\};\deg(a,b)=5)$ and it is
drawn as the underlining graph shown in Figure 45. The ten graphs, from
$S_{0}$ to $S_{9}$ in Figure 46, as well as $S_{x}$ and $S_{y}$ in Figure 47,
are congruent. So we can only deal with one of them in discussion of
4-colorable or not; because each of them is a necessary condition for $EP$
being non-4-colorable.

Let us still fix the subgraph $\Sigma^{\prime}$ and consider three vertices
$\alpha$, $\beta$ and $\gamma$ inside $\Phi$. We focus on two particular
MPS’s: $M^{+}_{a}$ and $M^{+}_{b}$ in Figure 49 where the superscript “+”
means $|M^{+}_{a}|=|M^{+}_{b}|=\omega+1$. We dare to ask a question: Are
$M^{+}_{a}$ and $M^{+}_{b}$ 4-colorable? The answer is yes, if non-4-colorable
$(EP;55)$ do exist. We will prove this interesting problem later.

Figure 49. $M^{+}_{a}$ and $M^{+}_{b}$

###  17.2. 4-colorable MPG’s with $(\\{a,b\\};\deg(a,b)=5)$

Let us think reversely. We focus on an 4-colorable MPG, say $M$, of any order
with $T\\!D:=(\\{a,b\\};\deg(a,b)=5)$, i.e., the underlining graph of $M$ is
as same $\Sigma$ as the ones in Figure 45. Of course, $M$ is a different
$\Sigma^{\prime}$ compared with $EP$. For $M$, we name
$\Omega:=v_{1}$-$v_{2}$-$c$-$v_{4}$-$v_{5}$-$d$-$v_{1}$ as the boarder between
$\Sigma$ and $\Sigma^{\prime}$.

Figure 50. Prototypes of red edge-coloring around vertex $a$

Figure 51. All possible types of RGB-tilings on $M$

Because $\Sigma^{\prime}$ is symmetric w.r.t. the vertical line and the
horizontal one, we will only explore those representatives of RGB-tilings on
$M$. We can first consider all possible R-tilings on $\Sigma$ to force $M$
4-colorable. We get three prototypes of red edge-coloring around vertex $a$ in
Figure 50. The details are given in Figure 51.

Depending on what $M$ is, at least one of these six patterns of RGB-tiling
(including their symmetric patterns) on $\Sigma$ can extend to
$\Sigma^{\prime}$, and then we can fulfill the assumption that $M$ is
4-colorable. Any kind of possible Kempe chains in $\Sigma^{\prime}$, which are
prepared for these six patterns of RGB-tiling on $\Sigma$, cannot create any
R/G/B odd-cycle.

######  Remark 17.9.

We can drop $[B2]$ from the list in Figure 51, because $[B2]\equiv|[A2]$.

######  Lemma 17.10.

(a): There is no intersection between
$\\{[S_{0}],[S_{1}],\ldots,[S_{9}],[S_{x}]\\}_{\text{sym}}$ and
$\\{[A1],[A2],[B1],[B3],[C1],[C2]\\}_{\text{sym}}$, where the subscript means
these two sets consist all symmetric images w.r.t. the vertical line and the
horizontal one. (b): Particularly there is not intersection between their own
$Co(\Phi)$. Otherwise, $EP$ with $T\\!D:=(\\{a,b\\};\deg(a,b)=5)$ is
4-colorable.

###### Proof.

Let us name
$ATLAS_{N}:=\\{[S_{0}],[S_{1}],\ldots,[S_{9}],[S_{x}]\\}_{\text{sym}}$
temporarily, but later we will modify this set without hurting this lemma.
Also $ATLAS_{4}:=\\{[A1],[A2],[B1],[B3],[C1],[C2]\\}_{\text{sym}}$. Clearly,
the subscripts $N$ and $4$ stand for non-4-colorable and 4-colorable.

For (a), they should no intersection. It need patience to check these two sets
in the coming subsection. Also, no intersection is a necessary condition for
non-4-colorablility, but not a sufficient condition.

As for (b), it raises another important question: Does the edge-color along
$\Phi$, namely $Co(\Phi)$, unique determine the 4-colorable property of
$M:=\Phi\cup\Sigma\cup\Sigma^{\prime}$? However, this new question is far more
than what we claim only for $(EP;55)$.

Sorry! This brief remark is not a real proof. The real proof of (a) is in the
next subsection. Part (b) is just a consequence of (a), because the
comprehensive study on $ATLAS_{\ast}$ do show that the types of $Co(\Phi)$
uniquely determine each element in $ATLAS_{N}\cap ATLAS_{4}$ and more that
that. The property of unique determination so far only works for $(EP;55)$ and
$(EP;Ptg)$. ∎

###  17.3. $ATLAS$ of Figures 46, 47, 51 and more

For convenience, all $[\ast]$ in this subsection is actually
$[\ast]_{\text{sym}}$. The main purpose of this subsection is to list all
kinds of $Co(\Phi)$ under synonyms and symmetries; then we can offer a proof
of Lemma 17.10(a) about $ATLAS_{N}$ and $ATLAS_{4}$.

According to Subsections 17.1 and 17.2, it is nature to ask: Does the union
set of those $Co(\Phi)$ in Figures 46, 47 and 51 consists of all possible
$Co(\Phi)$ provided that $Co(\Sigma^{\prime})$ is 4-colorable. The answer is
no, but this union set consists of nearly all.

By Lemma LABEL:RGB1-thm:evenoddRGB, the array $(\\#r,\\#g,\\#b)$ of numbers of
red, green and blue edges along $Co(\Phi)$ can only be $(0,0,6)$, $(0,2,4)$
and $(2,2,2)$ under synonyms. The cases of $(0,0,6)$ and $(0,2,4)$ are easy
and demonstrated by Table 1 systematically.

|  |  |
---|---|---|---
|  |  |
Table 1. $Co(\Sigma)$ and skeletons in $\Sigma^{\prime}$ for $(0,0,6)$ and
$(0,2,4)$

Notice that in this table skeletons are unnecessary for cases [A$\ast$],
[B$\ast$] and [C$\ast$], because they are for colorable for any kinds of
$K_{\ast}$ in $\Sigma^{\prime}$. However, we do draw a $K_{r}$ for case
$[X_{1}]$, which never showed up before555That is why we mark it by “X”.. We
also claim $[X_{1}]$ 4-colorable, because of Lemma 16.8.

To list all cases of $(2,2,2)$ under synonyms, we can refer to cases of
$(0,2,4)$ and then choose two blue edges along $\Phi$. But this way is so
tedious and twice the work with half the results. Let us consider the two
edges in same color adjacent or not (Y/N). So we shall follow four extra
requirements: $(Y,Y,Y)$, $(N,Y,Y)$, $(N,N,Y)$ and $(N,N,N)$. Now we will
demonstrate all cases in Table 2.

|  |  |
---|---|---|---
|  |  |
Table 2. $Co(\Sigma)$ and skeletons in $\Sigma^{\prime}$ for $(2,2,2)$

Notice that there is only one case for $(Y,Y,Y)$ under synonyms. We obtain
$[X_{2}]$, which never showed up before. Of course this $[X_{2}]$ is special.
Later we will find it ubiquitous in further study. The two yellow double-lines
are two $e$-diamonds of Type B involving three edge-colors; therefore we can
not get any information on $\Sigma^{\prime}$ from these two $e$-diamonds. It
is not a problem comes two or more $e$-diamonds. For instance, $[S_{x}]$ in
Figure 47 has two $e$-diamonds. The good thing is these two $e$-diamonds of
Type B involving two edge-colors. Even if $S_{x}$ comes out of nowhere, rather
than what we just showed that it is from $[S_{1}]$, we still can build up
$K_{g}|_{c}^{v_{1}}$ and $K_{g}|_{c}^{v_{5}}$.

######  Remark 17.11.

In the graph $[X_{2}]$ given in Table 2, we draw a dashed $K_{r}|_{c}^{v_{5}}$
on purpose. Actually, once [$X_{2}$] appears it must have (a): either
$K_{r}|_{c}^{v_{5}}$ or $K_{r}|_{d}^{v_{4}}$; and (b): either
$K_{g}|_{c}^{v_{1}}$ or $K_{g}|_{d}^{v_{2}}$. It is possible that four kinds
of combinations of (a) and (b) all suit for this $EP$ with
$T\\!D:=(\\{a,b\\};\deg(a,b)=5)$, but at least one combination exists. Without
loss of generality, we assume $K_{r}|_{c}^{v_{5}}$ appears in $[X_{2}]$. Then
we process ECS on $rGCL(cv_{4})$ and then obtain the second graph in Figure
52. The second graph ($[S_{3}]$, Type B) and the third graph ($[S_{3}]$, Type
A) have same $Co(\Phi)$, but only Type A can guarantee two Kempe chains:
$K_{g}|_{d}^{v_{2}}$ and $K_{b}|_{d}^{v_{4}}$. From the second graph to the
third graph, the process can be done by ECS or directly by _$\Sigma$
-adjustment_, which is a modification inside $\Sigma$ and will be introduced
later formally. Let us make the conclusion of this remark: If $[X_{2}]$
exists, then $[X_{2}]\cong[S_{3}]$. But so far the existence is not
guaranteed.

Figure 52. $[X_{2}]$ and $[S_{3}]$

######  Remark 17.12.

Our curiosity on $[X_{2}]$ has not ended yet. There are two possible blue
Kempe chains, namely $K_{b}|_{v_{1}}^{v_{5}}$ and $K_{b}|_{c}^{d}$, and at
least one exists666Be careful! They never co-exist; they might exist for
different RGB-tilings.. Therefore, we can perform two possible ECS and then
obtain $[S_{5}]$ and $[S_{x}]$ shown as the second graph and the third one in
Figure 53. Not we realize that $[X_{2}]$ connects to many different colleagues
in $ATLAS_{N}$

Figure 53. $[X_{2}]$ and $[S_{3}]$

######  Remark 17.13.

The second graph in Figure 53 has $K_{b}|_{v_{1}}^{v_{5}}$. It does not means
that every $[S_{5}]$ equips with $K_{b}|_{v_{1}}^{v_{5}}$. It is possible that
another $S_{5}$ RGB-tiling has $K_{b}|_{c}^{d}$. The above argument can also
apply on the third graph in Figure 53.

######  Remark 17.14.

Comparing two $[S_{3}]$ in Figure 46777Please, replace
$K_{g}|_{v_{2}}^{v_{4}}$ by $K_{g}|_{d}^{v_{2}}$; because we only guarantee
this green-connectivity. and in Figure 52 and under synonyms, we find that the
new one (latter one) has three Kempe chains of three different colors. Remark
17.11 offer a reason of the existence of this new $K_{r}|_{c}^{v_{5}}$. We
provide another reason. If there is no $K_{r}|_{c}^{v_{5}}$, then there should
be a $K_{r}|_{d}^{v_{4}}$ and then we can turn this $[S_{3}]$ to be $[X_{1}]$
in Table 2; thus this $EP\not\in e\mathcal{MPGN}4$ and a contradiction. Now we
realize how interesting and important Lemmas LABEL:RGB2-thm:deg5tangling and
16.8 are. One more important thing: thanks for this “another reason”, we can
say $[X_{2}]$ is obtained from $[S_{3}]$ by performing ECS on $rGCL(cv_{4})$
in Figure 52. So, the existence of $[X_{2}]$ is guaranteed. Otherwise, the
process that we did in Remark 17.11 bases on the assumption of existence of
$[X_{2}]$ and it is possible that $[X_{2}]$ does not exist. Now we complete
entire $ATLAS_{N}$ theoretically.

######  Remark 17.15.

Let us re-check $[S_{4}]$ in Figure 46. Using $\Sigma$-adjustment, we find a
new $K_{b}|_{v_{1}}^{v_{5}}$. This refinement has another reason. If there is
no $K_{b}|_{v_{1}}^{v_{5}}$, then there should be a $K_{b}|_{d}^{v_{4}}$ and
then we can turn the original $[S_{4}]$ (the left graph) to be to be [A2];
thus this $EP\not\in e\mathcal{MPGN}4$ and a contradiction.

Figure 54. $[S_{3}]$ and $\Sigma$-adjustment

Now finally we finish a proof of Lemma 17.10(a). Not only a proof but also we
list $ATLAS_{N}$ more precise with one more element $[X_{2}]$. Let us conclude
this whole section as following theorem:

######  Theorem 17.16.

Let $EP\in e\mathcal{MPGN}4$ with $T\\!D:=(\\{a,b\\};\deg(a,b)=5)$. Every
element in
$ATLAS_{N}:=\\{[S_{0}],[S_{1}],\ldots,[S_{5}],[S_{x}],[X_{2}]\\}_{\text{sym}}$
will appear by doing a series of ECS starting from $[S_{0}]$ or from any one
in $ATLAS_{N}$.

###### Proof.

Remark 17.14 has already shown the existence of $[X_{2}]$, because it can be
obtained from $[S_{3}]$. ∎

######  Remark 17.17.

Recall the interesting problem that we left in Figure 49. For symmetry, we
only show $M^{+}_{a}$ is 4-colorable. If non-4-colorable $(EP;55)$ do exist,
then the RGB-tiling $[S_{x}]$ exists. We only need the R-tiling of $[S_{x}]$
on $\Sigma^{\prime}$. Put this R-tiling on the same $\Sigma^{\prime}$ of
$M^{+}_{a}$ and also color 5 edges inside $\Sigma$ shown in Figure 55. Now the
whole R-tiling on $M^{+}_{a}$ has no odd-cycle. By Theorem
LABEL:RGB1-thm:4RGBtiling, $M^{+}_{a}$ is 4-colorable.

Figure 55. From $[S_{x}]$ to $M^{+}_{a}$

##  18\. Theory behind ECS on generalized canal rings

We have already performed ECS on generalized canal rings many times, but we
did not talk clearly about the theory. In this sections we explain our
standard of process (SOP) to perform ECS on generalized canal lines or rings,
and then investigate new Kempe chains in $\Sigma^{\prime}$.

###  18.1. Topic for discussion $T\\!D$ and boarder $\Omega$ in $EP$

Given a fixed $EP\in e\mathcal{MPGN}4$, let
$T\\!D:=(\\{u_{1},u_{2},\ldots,u_{k}\\};\text{requirements})$ consist of some
chosen vertices from $EP$ as the _topic for discussion_ , where _requirements_
set up the particular type of $u_{1},u_{2},\ldots,u_{k}$. We also use $T\\!D$
to represent the induced subgraph made by the vertices of $T\\!D$. Usually we
require this subgraph $T\\!D$ connected and solid, where“solid” means no hole;
and it had better to be 2-connected if $k\geq 4$. The _boarder_ $\Omega$
(sometimes $\Phi$) is a subgraph induced by the vertex set consists of all
surrounding neighbors of $T\\!D$. Clearly, $\Omega$ is a cycle surrounding
$T\\!D$, unless $T\\!D$ is so weird. Let $\Sigma:=\Omega\cup T\\!D$ and
$\Sigma^{\prime}:=EP-T\\!D$. Clearly $\Sigma\cap\Sigma^{\prime}=\Omega$. For
example $T\\!D:=(\\{v\\};\deg(v)=5)$ and
$\Omega:=v_{1}$-$v_{2}$-$\ldots$-$v_{5}$-$v_{1}$ in Figure 40.

Due to the definition of $e\mathcal{MPGN}4$ and Theorem
LABEL:RGB1-thm:eMPG4(b), a 4-semi-MPG $EP-\\{e\\}$ for any $e\in E(EP)$ is
4-colorable and there is at least an RGB-tiling on $EP-\\{e\\}$. By Theorem
LABEL:RGB2-thm:EPediamond2, RGB-tilings with Type A and Type B $e$-diamond
both exist and are congruent to each other in pairs. Please, recall our
premature concept of $ATLAS_{N}$ and $ATLAS_{4}$ in Section 17. To study
$(EP;T\\!D)$, we keep improving or refining these two sets. A _primary_ RGB-
tiling with a particular $e$-diamond, like $T_{\alpha}^{55}$ and
$T_{\beta}^{55}$ in Figure 45, are the original members of $ATLAS_{N}$, which
are two different RGB-tilings on $EP-\\{ab\\}$. Actually the _primary_ 888The
_primary_ RGB-tilings and the _initial_ ones are different. Please, wait for
the definition of the latter ones. RGB-tilings for the discussion on
$(EP;T\\!D)$ can be all inner edges $e$ in $\Sigma$, and then we define the
_primary atlas_ of RGB-tilings w.r.t. $(EP;T\\!D)$:

$\displaystyle ATLAS_{N}(EP;T\\!D)$ $\displaystyle\overset{\text{\tiny
tmp}}{:=}$ $\displaystyle\\{T^{T\\!D}\mid\text{ RGB-tilings, either Type A or
Type B,}$ $\displaystyle\text{on $EP-\\{e\\}$ for $e\in
E(\Sigma)-E(\Omega)$}\\}.$

For example, see $ATLAS_{N}$ in the proof of Lemma 17.10.

######  Remark 18.1.

Why did we only consider Type A for our initial $ATLAS_{N}$ in the last
section? Because we get benefit from $T\\!D$ containing some vertices of
degree 5 and any Type B $e$-diamond with $e$ incident to these vertices degree
5 can be transformed to Type A $e^{\prime}$-diamond without changing
$Co(\Phi)$ and the associating skeleton.

On the other hand, to attack the non-4-colorability of $(EP;T\\!D)$, we
consider all possible local 4-colorable functions on $\Sigma$, each of which
is also an RGB-tiling on $\Sigma$. So we construct the following set:

$\displaystyle ATLAS_{4}(T\\!D)$ $\displaystyle\overset{\text{\tiny tmp}}{:=}$
$\displaystyle\\{T^{T\\!D}\mid\text{ RGB-tilings on $\Sigma$}\\}.$

######  Remark 18.2.

The main idea of whole project is to prove by contrapositive with the
assumption that $EP$ exists. The existence of $(EP;T\\!D)$ derives every
element in $ATLAS_{N}(EP;T\\!D)$ must exist and $ATLAS_{4}(T\\!D)$ must be
empty. Once we find $ATLAS_{N}(EP;T\\!D)\cap ATLAS_{4}(T\\!D)$ non-empty, then
$(EP;T\\!D)$ is impossible; but not every $EP$. The edge-color $Co(\Omega)$
plays an important role on checking $ATLAS_{N}(EP;T\\!D)\cap
ATLAS_{4}(T\\!D)=\emptyset$ or not.

Not just for one particular _abandoned_ edge $e$, we might consider a
particular set of _abandoned_ edges, denoted by $\\{\ast\\}$ when the elements
are not chosen yet, and consider any RGB-tiling on $EP-\\{\ast\\}$, i.e., a
combination of $e$-diamonds with Types A and B. There are two different reason
to concern about a set $\\{\ast\\}$ containing multiple edges:

  1. (1)

This new RGB-tiling on $EP-\\{\ast\\}$ is obtained from one of the primary
RGB-tilings. For example, $[S_{x}]$ in Remark 17.5.

  2. (2)

Sometimes we are forced to check all possible cases of $Co(\Omega)$. We might
find some $Co(\Omega)$ that were not investigated yet. So, after studied they
can be sorted into $ATLAS_{N}(EP;T\\!D)$ or $ATLAS_{4}(T\\!D)$. For example,
$[X_{1}]$ and $[X_{2}]$ in Subsection 51. However, $[X_{2}]$ obtained from one
of the primary RGB-tilings is still very important.

The _secondary_ $ATLAS_{N}(EP;T\\!D)$ consists of these new RGB-tilings on
$EP-\\{\ast\\}$ (non-4-colorable on $EP$) together with all primary ones;
similarly for the _secondary_ $ATLAS_{4}(T\\!D)$.

Yes, we do have the _tertiary_ $ATLAS_{N}(EP;T\\!D)$. In this extended
collection, we consider $\\{\ast\\}$ to be a subset of $E(\Sigma)$; however
the edges in $\\{\ast\\}$ still form multiple $e$-diamonds of Type A and Type
B. For instance, $Co_{\alpha}(Ptg)$, $Co_{\beta}(Ptg)$ and $Co_{\gamma}(Ptg)$
in Figures 43 and 44.

######  Remark 18.3.

Why do we always emphasize that new (secondary and tertiary) RGB-tilings on
$EP-\\{\ast\\}$ are obtained from a primary one? Because we assume that
$(EP;T\\!D)$ exists, thus every primary RGB-tilings on $EP-\\{e\\}$ exists by
Theorem LABEL:RGB2-thm:EPediamond2. We have to guarantee all element in the
secondary and the tertiary sets exist under this assumption. Therefore,
$ATLAS_{N}(EP;T\\!D)\cap ATLAS_{4}(T\\!D)=\emptyset$ or not is really a
crucial point to judge $(EP;T\\!D)$.

###  18.2. The magic of the yellow double-lines and congruence relation

The magic of the yellow double-lines (_abandoned_ edges) is that replacing it
by either red, green or blue, we will get an odd-cycle of the same color,
which is called a _Kempe chain_. Given an $e$-diamond, for Type A, there are
two non-trivial Kempe chains of different colors; as for Type B, there is only
one. Kempe chains are just representatives because it is possible that a
clusters of red/green/blue paths linking the two end-vertices of $e$. In other
words, a red Kempe chain represents red-connected property in
$\Sigma^{\prime}$. Please, see Section LABEL:RGB2-sec:tanglingProperty for
details.

When we have multiple $e$-diamonds, the Kempe chains in this RGB-tiling on
$EP-\\{\ast\\}$ need to judge case-by-case. For instance,$[S_{x}]$ in Figure
47 and $[X_{2}]$ in Remark 17.11.

Following Remark 18.3, we understand that the co-existence of certain RGB-
tilings on different $EP-\\{\ast\\}$ built by congruence relation is so
important. Congruence relation is based on performing ECS on a canal ring or a
generalized canal ring. Performing ECS on a canal ring will create a new RGB-
tiling on $EP-\\{\ast\\}$ without changing $\\{\ast\\}$; however performing
ECS on a generalized canal ring will change to a new $\\{\ast\\}$. The former
is easily passed on theory, but the latter need to be explained more
precisely.

Let us consider an RGB-tiling $T^{T\\!D}_{\alpha}(EP-\\{e_{\alpha 1},e_{\alpha
2},\ldots\\})$, where $\\{e_{\alpha 1},e_{\alpha 2},\ldots\\}$ is a set of
inner edges of $\Sigma$ such that no two of them in a single triangle. Suppose
a generalized canal ring $rGCL$ is a part of
$T^{T\\!D}_{\alpha}(EP-\\{e_{\alpha 1},e_{\alpha 2},\ldots\\})$ and it is the
one we would like to perform ECS to get a new RGB-tiling
$T^{T\\!D}_{\beta}(EP-\\{e_{\beta 1},e_{\beta 2},\ldots\\})$. This $rGCL$ must
have segments of two kinds. The first kind is along a red Kempe chain
$K_{r}|_{u}^{v}$ (or maybe more) in $\Sigma^{\prime}$. Thus
$rGCL\cap\Sigma^{\prime}$ must be a normal red canal line(s) and performing
ECS on $T^{T\\!D}_{\alpha}$ will still make the new $T^{T\\!D}_{\beta}$ still
an RGB-tiling on $\Sigma^{\prime}$. Notice that the tangling property in
Section LABEL:RGB2-sec:tanglingProperty might happen for this reason. Here we
bring back an important question: Besides degree 5, does there any other
situation have tangling property?

The segment(s) of the second kind is the part $rGCL\cap\Sigma$ and this is the
real “generalized” part. Let us review the rules of ECS on a red generalized
canal line or ring:

  * •

Switch edge colors of green and blue, just like what we do for a normal red
canal line;

  * •

Switch edge colors of red and yellow double-line, and this switching rule is
what we perform for the “generalized” segment.

  * •

To perform edge-color-switching on (or along) a green/blue generalized canal
ring, we just apply the two items above, under symmetry of three colors.

After ECS, by the second rule above, some yellow edges in $\\{e_{\alpha
1},e_{\alpha 2},\ldots\\}$ turn to be red; however in view of R-tiling on
$EP$, they are assumed to be red already. The remained unchanged yellow edges
in $\\{e_{\alpha 1},e_{\alpha 2},\ldots\\}$ together with the some original
red edges that passed by $rGCL$ form the new yellow-edge-set $\\{e_{\beta
1},e_{\beta 2},\ldots\\}$. With this new yellow-edge-set, we shall investigate
new $K_{g}$ and $K_{b}$. This this the key point of our ECS process. We
preserve all $K_{r}\cap\Sigma^{\prime}$, and try to build new
$K_{g}\cap\Sigma^{\prime}$ and $K_{b}\cap\Sigma^{\prime}$ for
$T^{T\\!D}_{\beta}$. Now we can consider $T^{T\\!D}_{\beta}(EP-\\{e_{\beta
1},e_{\beta 2},\ldots\\})$ and use a generalized canal ring $gGCL$ or $bGCL$
to perform the next ECS. The sequence of process is just like what did in
Figure 46.

######  Remark 18.4.

Recall the red Kempe chain $K_{r}|_{u}^{v}$ described in the last two
paragraph. Suppose that edges $uu^{\prime}$ and $vv^{\prime}$ are along
$\Omega$ and crossed by $rGCL$. According the first rule above, the colors on
$uu^{\prime}$ and $vv^{\prime}$ are just switched between green and blue, and
then $Co(\Omega)$ is changed. Thus, the sequence of ECS process can explore
many different kinds of $Co(\Omega)$ for $(EC;T\\!D)$.

Besides Figure 46, we also explored $ATLAS_{\ast}$ in Subsection 17.3. Without
this hard work, we probably cannot find the interesting $[x_{1}]$ and
$[X_{2}]$. Do we really need to explored $ATLAS_{\ast}$? It depends on what
kind of $T\\!D$ that we discuss. The more fundamental structure of $T\\!D$,
the more details we need to know.

###  18.3. $\Sigma$-adjustments and $\\{\ast\\}$

In the last subsection we wrote: We preserve all $K_{r}\cap\Sigma^{\prime}$,
and try to build new $K_{g}\cap\Sigma^{\prime}$ and $K_{b}\cap\Sigma^{\prime}$
for $T^{T\\!D}_{\beta}$. The general way to do is observing the new set
$\\{e_{\beta 1},e_{\beta 2},\ldots\\}$ in $\Sigma$; however, we have many
different ways to build new $K_{g}\cap\Sigma^{\prime}$ and
$K_{b}\cap\Sigma^{\prime}$ as skeleton, and we had better do our best to find
them. For example, the red Kempe chain $K_{r}|_{c}^{v_{5}}$ of $[S_{3}]$, in
Table 2 or in Remark 17.14, is obtained by exclusive law.

The method of $\Sigma$-adjustments has been already used in Remarks 17.5,
17.11 and 17.15. There are two major methods to perform a $\Sigma$-adjustment:

  1. (1)

Find any generalized canal ring inside $\Sigma$ and perform ECS. Then we have
new set of abandoned edges $\\{e^{\prime}_{\beta 1},e^{\prime}_{\beta
2},\ldots\\}$ in $\Sigma$ to build new $K_{g}\cap\Sigma^{\prime}$ and
$K_{b}\cap\Sigma^{\prime}$.

  2. (2)

Just keep $Co(\Omega)$ of this moment unchanged. Try to re-arrange a new
single color tiling inside $\Sigma$. Then according $Co(\Omega)$ to complete
the other two edge-coloring. Most of time, we cannot obtain an RGB-tiling on
$\Sigma$ but one on $\Sigma-\\{\ast\\}$. Now try to build new
$K_{g}\cap\Sigma^{\prime}$ or $K_{b}\cap\Sigma^{\prime}$.

The reader can practice method (1) using $[S_{1}]$ or $[S_{4}]$, and a red
generalized canal ring inside $\Sigma$. All [A1], [A2], [B1], [B2], [B3],
[C1], [C2] were made by method (2) without any abandoned edge. Also $[X_{1}]$
and $[X_{2}]$ were studied by method (2) at the very beginning.

Working on $ATLAS_{\ast}$ in Subsection 17.3 is so tedious, but the job in
Subsection 17.1 is standard.

Because $EP$ is the extremum or the smallest non-4-colorable MPG, we can only
4-color $EP-\\{e\\}$ and some time $EP-\\{\ast\\}$. The theory of $e$-diamond
is much easier, for it can be only be Type A and Type B, which are co-
existing. A large set $\\{\ast\\}$ of abandoned edges make a coloring or an
RGB-tiling on both $\Sigma$ and $\Sigma^{\prime}$, as well as $Co(\Omega)$,
more complicated. Also we need to be very careful: Without linking to a
certain congruent RGB-tiling $T_{\alpha}^{T\\!D}(EP-\\{e\\})$, we have no
right to guarantee the existence of $T_{\beta}^{T\\!D}(EP-\\{\ast\\})$.

##  19\. Three degree 5 vertices in a triangle

Let us consider the situation that three vertices of degree 5 in $EP$ form a
triangle. Our have new $T\\!D:=(\\{a,b,c\\};\deg(a,b,c)=5)$ or “$5^{3}$” in
short that consists of three vertices of degree 5 shown in Figure 56 and
$\Omega:=d$-$v_{1}$-$v_{2}$-$\ldots$-$v_{5}$-$d$.

By Lemma 17.8 we choose the first graph $[T_{\alpha}^{55}]$ in Figure 45 to
discuss. The following two graphs, $[T_{1}^{5^{3}}]$ and $[T_{2}^{5^{3}}]$,
are determined by $cv_{3}$ being blue or green. However, given $cv_{3}$ blue,
we see a 5-cycle $K_{g}\cup\\{ab\\}$. By Lemma 16.8 or the tangling property
for $EP$ with $\deg(a,b)=5$, we have a contradiction.

Figure 56. Only $[T_{2}^{5^{3}}]$ is is good for $EP$, not $[T_{1}^{5^{3}}]$

Thus, only $[T_{2}^{5^{3}}]$ can be the proper RGB-tiling for this
$(EP;T\\!D)$. In addition, we claim that the red dashed path exists. We simply
re-arrange a new red tiling inside $\Sigma$ and treat green/blue as black. The
new red tiling on $EP$ is shown as the third graph
$[{T_{2}^{5^{3}}}^{\prime}]$ and there must have at least a red odd-cycle
crossing $\Sigma$. The only way is the red path $K_{r}|_{v1}^{v_{3}}$.

Just for fun, the reader can re-arrange another new red tiling inside $\Sigma$
by setting $d$-$a$-$v_{2}$ and $v_{3}$-$c$-$b$-$v_{5}$ red, and then exams the
new red odd-cycle crossing $\Sigma$. We leave the reader to draw this result.

######  Lemma 19.1.

Let $a,b,c$ be three vertices in a triangle of $EP$ with $\deg(a,b,c)=5$.
There is only one congruent class of RGB-tilings on $EP$. This congruent class
has a representative shown as $[T_{2}^{5^{3}}]$ in Figure 56. Please, turn the
red dashed line in $[T_{2}^{5^{3}}]$ solid.

As different way to prove the existence of the red dashed in Figure 56 is
given as the following process. In Figure 57, starting with the original
$[T_{2}^{5^{3}}]$, we perform two ECS on a $rGCL$ and then on a $bCL$. The
result $[T_{2}^{5^{3}}+2_{rb}]$ is given as the third graph. Since we use a
red generalized canal ring crossing $\Sigma^{\prime}$ and the second blue
canal ring is all inside $\Sigma$. So the new red Kempe chain
$K_{r}|_{v_{1}}^{v^{3}}$ is supposed to exist in $[T_{2}^{5^{3}}]$ before we
change it.

Figure 57. Another way to realize $K_{r}|_{v_{1}}^{v^{3}}$

The third graph above is very interesting and important; so we give it a
special name: $[T_{\alpha}^{5^{3}}]$. In this RGB-tiling, all edges along
$\Phi$ are blue with three degree 5 vertices inside. What a symmetric
structure and edge-coloring! Wait! the graph $[T_{\alpha}^{5^{3}}]$ in Figure
57 is not really symmetric. Yes, we do miss a green Kempe chain
$K_{g}|_{v_{3}}^{v_{5}}$. Symmetry is not the reason that
$K_{g}|_{v_{3}}^{v_{5}}$ exists. The reason can be found in Figure 58. Also
notice that to draw $K_{r}|_{v_{1}}^{v_{3}}$ together with
$K_{r}|_{v_{1}}^{v_{5}}$ is not different to $K_{r}|_{v_{1}}^{v_{3}}$ together
with $K_{r}|_{v_{3}}^{v_{5}}$; or even to draw $K_{r}|_{v_{1}}^{v_{5}}$
together with $K_{r}|_{v_{3}}^{v_{5}}$. Because what we need is that $v_{1}$,
$v_{3}$ and $v_{5}$ are red-connected and also green-connected.

Again, just for fun, we develop three congruent RGB-tilings on $EP-\\{e\\}$
for $e=av_{1},bv_{5},cv_{3}$ in Figure 58.

Figure 58. Three congruent RGB-tilings; All of them are $[T_{\alpha}^{5^{3}}]$

######  Lemma 19.2.

Let $EP\in e\mathcal{MPGN}4$ with $a,b,c\in V(EP)$ in a triangle and
$\deg(a,b,c)=5$. Three congruent RGB-tilings $[T_{\alpha}^{5^{3}}]$ shown in
Figure 58 must exist.

###  19.1. Four degree 5 vertices in a diamond

Finally, we want to finish our interesting question: Can a diamond in $EP$
have all its four vertices degree 5?

######  Theorem 19.3.

Let $a,b,c,d$ be four vertices in a diamond in $EP$. It is impossible that all
of them are degree 5.

###### Proof.

Now $T\\!D:=(\\{a,b,c,d\\};\deg(a,b,c,d)=5)$ or $5^{4}$ in short, and
$\Omega:=v_{1}$-$v_{2}$-$\ldots$-$v_{6}$-$v_{1}$ be the 6-cycle of the
neighbors of $T\\!D$.

Let us adopt the second graph $[T_{2}^{5^{3}}]$ in Figure 56 to fit
$\\{a,b,c\\}$ and $\\{a,b,d\\}$ and then we obtain the only initial status
$[T^{5^{4}}]$ as in Figure 59. Before we proceed the major proof, a very minor
check need to be taken care: $v_{3}\neq v_{6}$. Theorem
LABEL:RGB2-thm:trivial4cycle offers a proof. Additionally the red-connectivity
of $v_{1}$, $v_{3}$ and $v_{5}$, and then these three vertices are red-
disconnected with $v_{6}$. This fact offers another proof for $v_{3}\neq
v_{6}$. Wait! We have never checked $v_{1}\neq v_{4}$ $v_{1}\neq v_{5}$, etc.
Actually we should prove these facts before. Lemma LABEL:RGB1-thm:nontrivial3
offers a proof for these simple cases.

Figure 59. A diamond with four degree 5’s in $EP$

Now we simply re-arrange a new red tiling inside $\Sigma$ shown as the second
graph in Figure 59. The second graph offers an R-tiling without odd-cycle. If
there is a new cycle, then it must cross $\Sigma$. First,
$K_{r}|_{v_{1}}^{v_{5}}\cup\\{dv_{1},dv_{5}\\}$ is an even-cycle. The path
$v_{2}$-$a$-$b$-$v_{4}$ can not fulfill a bigger cycle because it is blocked
by $K_{r}|_{v_{1}}^{v_{3}}$. The last thing to consider is: What about there
exists $K_{r}|_{v_{5}}^{v_{3}}$ (red dashed line)? Well, if it exists, then
the length is even by the first graph where $v_{5}$-$v_{4}$-$v_{3}$ is length
2 and all blue. Thus the big cycle $K_{r}|_{v_{1}}^{v_{3}}\cup
K_{r}|_{v_{5}}^{v_{3}}\cup\\{dv_{1},dv_{5}\\}$ is even length. By Theorem
LABEL:RGB1-thm:4RGBtilingGeneralization(d), an R-tiling∗ on an MPG must induce
a 4-coloring function. Now we has a contradiction and the proof is done. ∎

###  19.2. Three degree 5 vertices in a triangle, continued

Let us back to $T\\!D:=(\\{a,b,c\\};\deg(a,b,c)=5)$ with $a,b,c$ adjacent.
First we need to refer to Lemma 19.2. Figure 58 demonstrates three equivalent
RGB-tilings in $\Sigma^{\prime}$ of $T\\!D$, i.e., a necessary skeleton in
$\Sigma^{\prime}$ provided all edges along $\Omega$ blue. Let us redraw that
skeleton in $\Sigma^{\prime}$ but leave every edge inside $\Sigma$ black as
the first graph in Figure 60. There must be six vertices, say
$u_{1},u_{2},\ldots,u_{6}$, surrounding $T\\!D$. By Theorem 19.3,
$\deg(d,v_{2},v_{4})\geq 6$. So, here we assume the minimum situation
$(\ast)$: $\deg(d,v_{2},v_{4})=6$ and $\deg(v_{1},v_{3},v_{5})=5$. We shall
consider a new topic for discussion $\hat{T\\!D}$ who has the vertex set
$\\{a,b,c,d,v_{1},\ldots,v_{5}\\}$ and the requirement as the situation
$(\ast)$; and then a new $\hat{\Omega}:=u_{1}$-$u_{2}$-$\ldots$-$u_{6}$; also
new $\hat{\Sigma}$ and $\hat{\Sigma}^{\prime}$ inside and outside of
$\hat{\Omega}$ respectively. Please, see the second graph in Figure 60.

The second graph is the only feasible RGB-tiling on $\Sigma^{\prime}$ (not
only on $\hat{\Sigma}^{\prime}$) under synonyms. Particularly all edges in
$\hat{\Omega}$ must be blue. Now we find a blue canal ring $bCL$ in between
$\Omega$ and $\hat{\Omega}$. After performing ECS on this $bCL$, we obtain a
new RGB-tiling on $\Sigma^{\prime}$ shown as the third graph in Figure 60. Not
only that, we can do $\Sigma$-adjustment by coloring paths
$v_{1}$-$a$-$b$-$v_{5}$ and $v_{2}$-$c$-$v_{4}$ red. Finally we obtain a brand
new R-tiling without red odd-cycle. Please, check the only red cycle crossing
$\hat{\Sigma}$. It must be even length.

######  Lemma 19.4.

Let $EP\in e\mathcal{MPGN}4$ with $a,b,c\in V(EP)$ in a triangle and
$\deg(a,b,c)=5$. See Figure 60. It is impossible that the surrounding vertices
along $\Omega:=d$-$v_{1}$-$v_{2}$-$v_{3}$-$v_{4}$-$v_{6}$ have degree
property: $\deg(d,v_{2},v_{4})=6$ and $\deg(v_{1},v_{3},v_{5})=5$.

Figure 60. New $\hat{T\\!D}$: a union of $5^{3}$ and the surrounding
$(56)^{3}$

Our further study shows a more stronger property as follows:

######  Lemma 19.5.

Let $EP\in e\mathcal{MPGN}4$ with $a,b,c\in V(EP)$ in a triangle and
$\deg(a,b,c)=5$. Please, refer to the second graph in Figure 60 and the most
part of the hypothesis in Lemma 19.4. This time we only assume $\deg(v_{1})=5$
and $deg(d)=6$ in addition, while $deg(v_{2},v_{4})\geq 6$ (by Theorem 19.3)
and $deg(v_{3},v_{5})\geq 5$ are given automatically. It is impossible $EP\in
e\mathcal{MPGN}4$.

This new result will be proved in the near future.

##  20\. No two degree 5 vertices adjacent; We wish.

We have a dream to prove the following conjecture that covers all previous
results in this paper. Once we thought we did it, but a bug came out. However,
we would like demonstrate our false proof.

######  Conjecture 20.1.

Are there any two degree 5 vertices adjacent in $EP$? No way!

Let $EP\in e\mathcal{MPGN}4$. The given situation is that
$T\\!D:=(\\{a,b\\};\deg(a,b)=5)$ or $55$ in short. Then we have
$\Omega:=d$-$v_{1}$-$v_{2}$-$c$-$v_{4}$-$v_{5}$-$d$.

Now we create a new MPG $\hat{EP}$ from $EP$. We remove vertices $a$ and $b$,
and then merge $v_{2}=v_{4}$. Notice that $v_{2}$ and $v_{4}$ are not adjacent
in $\Sigma^{\prime}$; otherwise the 4-cycle $a$-$b$-$v_{4}$-$v_{2}$-$a$ must
form a diamond, but vertex $c$ say no. Please, see Theorem
LABEL:RGB2-thm:trivial4cycle. This merging also makes $v_{2}c=v_{4}c$ and this
fact will cause $v_{2}c$ and $v_{4}c$ have same edge-color in the original
$EP$. This merging also creates a new 4-outer facet
$\Phi:=d$-$v_{1}$-$v_{2}$-$v_{5}$-$d$. In addition, we set a new edge
$v_{1}v_{5}$ for $\hat{EP}$.

Thanks for the existence of $[\underline{S_{1}}]$ on $\Sigma^{\prime}$ of
$EP$. Thus, in Figure 61 we have two synonyms RGB-tilings, (A) and (B), on
$\hat{EP}$, which are of course Type A with $e$-diamond and $e=v_{1}v_{5}$.

Figure 61. Merging $v_{2}=v_{4}$

The case (C) is the last one we need to consider Type A with $e$-diamond on
$\hat{EP}$. However, it does not exist because of the last graph is a
4-colorable B-tiling on $EP$ in Figure 61. Clearly this B-tiling is restored
from (C).

If we consider Type A condition is a sufficient condition for this $\hat{EP}$
being non-4-colorable, then we obtain a contradiction for $|\hat{EP}|<|EP|$.
What a nice proof for Conjecture 20.1. Unfortunately Type A condition is not a
sufficient condition. Please, see False Conjecture LABEL:RGB2-thm:4bsufnes.

Thank for $ATLAS_{N}(EP;T\\!D)$ in Subsection 17.3. We find that $[S_{2}]$ can
offer a Type C $e$-diamond for $\hat{EP}$. Please, see Figure 62. By Theorem
LABEL:RGB2-thm:4ColorableIfandOnlyIf or directly by the second graph,
$\hat{EP}$ is 4-colorable.

Figure 62. Merging $v_{2}=v_{4}$

##  21\. What are next steps by this renewal approach

Study $T\\!D$, many different $T\\!D$. For instance $T\\!D$ consists of two or
three adjacent vertices of degree 5 or 6. Actually studying the distribution
of degrees along $\Omega$ or even the secondary layer $\Omega^{2}$, especially
those vertices of degrees at least 7, is our goal.

The setting of $\hat{T\\!D}$ in Subsection 19.2 is the minimum situation for
$\Omega$. There are many different settings for $\Omega$ to discuss. That will
be a new chapter of our study in the near future.

The more vertices in $T\\!D$ are or precisely the larger $\sum_{v\in
T\\!D}\deg(v)$ is, the more complex $ATLAS_{N}(EP-\\{\ast\\})$ is. To reduce
complexity, Lemma 17.8 uses congruence relation between elements in
$ATLAS_{N}(EP-\\{\ast\\})$.

## References

  * [1] A.B. Kempe , On the Geographical Problem of the Four Colours, Am. J. Math. 2 (1879), 193–220.
  * [2] S.-C. Liu, The Neighbors of all Degree 5s’ on the Extremal MPG, https://www.math.sinica.edu.tw/www/seminar/sem20_his_e.jsp?year=2020, item 10.