A Pure Mathematical Proof of the 4-Colour Theorem

Jun Wang

doi:10.26717/BJSTR.2023.52.008323

Review ArticleOpen Access

A Pure Mathematical Proof of the 4-Colour Theorem Volume 52- Issue 5

Jun Wang*

Master Of Condensed Matter Physics of Sun Yat-Sen University, China

Received: September 06, 2023; Published: September 19, 2023

*Corresponding author: Jun Wang, Master of Condensed Matter Physics of Sun Yat-Sen University, China

DOI: 10.26717/BJSTR.2023.52.008323

Abstract PDF

ABSTRACT

This work “A Pure Mathematical Proof of the 4-Colour Theorem” is related to the previous proof assited by computer. “Triangulations of Euler Convex Polygon” provides a fresh beginning point for the proof. The central concept is to discover an extended invariance property of Standard Graph’s boundary, which is described as “3-Colour All Phase States (3CP)” in this work and it is demonstrated that the Standard Graph’s boundary and sub-bound are 3CP and 4-colorable (4-3CP) via the Expanded Operation e(+, pi) and e(-, pi). It’s exciting that this regularity was discovered for the first time and the 4-3CP invariance can naturally derive the 4-Colour Theorem. The majority of the definitions, theorems and proof strategies are shown in this work.

Keywords: 4-Colour Theorem; Standard Graph; Bound; Sub-bound; 3CP; e(+, pi); e(-, pi); Triangulations

Introduction

The 4-Colour Theorem states that every map can be coloured using only four colours and no two adjacent regions have the same colour. The initial problem was first posed in the mid-19^th century by Francis Guthrie. Guthrie noticed that four colours were sufficient to colour the map, and he wondered if this was true for every map. Many mathematicians attempted to solve the problem, but rigorous mathematical proof remained elusive. It became one of the most famous mathematical problems of the 20^th century and Kenneth Appel and Wolfgang Haken finally solved computer-aided proof in 1976. This proof was considered controversial due to the extent of the computer assistance required. The 4-Colour Theorem has important applications in real-world situations, such as in scheduling and timetabling problems. It also demonstrates the power and elegance of mathematical reasoning, as well as the importance of collaboration and innovation in solving complex problems. We describe a specific class of graphs (Appendix Figure 1) called Standard Graphs (SG), which are constructed by the Expanded Operations e(+, p_i) and e(-, p_i), which are used to replace planar graphs since they may have a significant number of unsaturated links and lack uniformity. The Proof begins with "Triangulations of Euler Convex Polygons": convex polygons can be sliced into multiple triangles (Euler obtains the famous Catalan Number [1] by counting the number of triangulations of convex polygons [2]). In this article, we defined all the possible triangulations sets of convex polygons (denoted by "bound") as "All Phase States (AP)". If the boundary of any Standard Graph (SG) is All Phase States (AP) and 4-colorable, the 4-Colour Theorem will be established [3]. Unfortunately, the All Phase States (AP) property of the boundary cannot keep Invariance during the Expanded Operation e(+, p_i) (denoted by "IEO"), which implies that the All Phase States (AP) property is incomplete. Thus the boundary of the Standard Graph must have a cryptic property that can satisfy both the. All Phase States (AP) and IEO. Finally, I find that the Standard Graph's boundary satisfy 3CP and 4-colorable (denoted by "4-3CP") and it is proven 4-3CP is IEO. This article's primary goal is to attest the Standard Graph’s boundary J(m) and all its sub-bounds set {J(m’)} are 4-3CP.

Figure 1 Appendix Figure 1: Definition

Bound

Set a cycle C(P_m, L_m), P_m = {p₁, p₂, ···, p_m}, L_m = {p₁p₂, p₂p₃,···,p_m-1p_m, p_mp₁}, m ≧ 3, cycle C divides the plane into two connected domain: inside and outside, then we call the cycle C be a bound (Figure 1), denoted by J(m) or J(P_m). |J(m)| = m is the number of points of J(m), ||J(m)|| = m is the number of links of J(m). There are two types of link: real link "—" (p₁-p₂, p₂-p₃,···) and virtual link "···" (p₁···p₄, p₃···p₅, ···) although the two points aren’t linked by a real link, the virtual link is exist between them cause they are colored differently. Set a bound J(m), we get points set Pm’ ⊆ Pm to form some new bounds J(m’), J₁, J₂, ···, (without cut links and loops), which are called sub-bounds of J(m). The J(m’), J₁, J₂, ··· is sub-bounds set {J(m’)} of J(m). The sub-bounds set {J₁, J₂, ···} is called com-bound

of J(m’) in J(m).

Figure 2 Figure 1: Bound.

All Phase States

We defined a triangulation of convex polygons as a link state and provided samples of J(3)-J(7) in Figure 2. If the bound J(m) contains all link states, we call J(m) all phase states (AP). The all link states number of J(m+2) is

(C(m) is Catalan Number). Set {J(m’)} be a sub-bound set of J(m), it is simple to demonstrate that all of the sub-bounds set {J(m’)} are AP if and only if J(m) is AP. The sub-bounds set {J(m’)} is AP, which means that the sub-bound J(m’) ∈ {J(m’)} is AP and independent.

Figure 3 Figure 2: Link states of J(3)-J(7).

The 3-Colour All Phase States (3CP)

Let J(Pm) be the boundary of Standard Graph SG (Figure 3), Y is the colouring solution set family of J(P_m), if Y can make the bound J(P_m) be AP and ∃ 3Y∈ Y, we call J(Pm) 3-Colour All Phase State (3CP). An example of 3CP is provided bellow (Figure 4). If we have enough time to test all of the Standard Graph conditions, we will discover that the boundary of every Standard Graph is 3CP and 4-colorable (Appendix Text). It's exciting that this regularity was discovered for the first time and the 4-3CP invariance can naturally derive the 4-Colour Theorem.

Figure 4 Figure 3: An example of the 3-Colour All Phase States (3CP).

Figure 5 Figure 4: J(P_m) of SG.

The 4-3CP Conjecture

The conjecture is described as follows：

4-3CP Conjecture: ∀ standard graph SG, J(m) is the boundary of SG, let Y is the colouring solution set family of J(m), {J’(m)} is sub-bounds set of J(m), Y can make：

J(m) be 3CP,

{J’(m)} be 3CP,

Let

link

form sub-bounds

and

if x scans on

is 3CP.

Proof

By Exhaustive Method, It’s Easy to See

Element e = SG(1), J(3) conform to 4-3CP Conjecture.

SG(2), J(4) conform to 4-3CP Conjecture.

SG(3), J(3) conform to 4-3CP Conjecture.

Set a Standard Graph SG, the boundary J(P_m) of SG, the colouring solution set family Y of J(P_m), |Y|≦4, J(P_m) and it’s sub-bounds J(P_m’) conform to the 4-3CP Conjecture. Then add an element e(ade) (points a, d, e form a triangle) on the J(P_m) to form a new boundary denoted by J(a + P_m) = J(P_m) + e(ade) (d, e ∈ J(P_m), d-e, a is new). According to the Points Scanning Method (Appendix Figure 3), it’s easy to prove J(a + P_m) is 3CP and 4-colorable, so 4-3CP Conjecture (2) is proven. Next, we shall prove the sub-bounds set {J(a + P_m’)} of J(a + P_m) is 3CP and 4-colorable: When |Y| = 3, J(P_m) is AP equals to J(P_m) is 3CP. Since J(P_m) is AP, so the sub-bounds set {J(P_m’)} is AP, and Y(J(P_m’)) ∈ Y, |Y(J(P_m’))| = |Y| = 3, so {J(P_m’)} is 3CP. Then we shall prove when |Y| = 4, the sub-bounds set {J(a + P_m’)} of J(a + P_m) is 3CP.

Figure 6 Appendix Figure 3: J(m) Links Scanning Method.

When the New Point A ∉3-Colour Sub-Bound Of J(A+P_m)

Take any n points P_n = {p₁, p₂, p₃, ···, p_n} ⊆ P_m, link p₁-p₂, p₂-p₃, ···, p_n-1-p_n, form (n-1) sub-bounds J(p₁-p₂), J(p₂-p₃), ···, J(p_n-1-p_n), and take any point x, x∈P_n, x ≠ p₁, p_n, link x with p₁, p_n form two sub-bounds J(x→p_n) and J(p₁→x); link x with d, e form J(x→p_nd), J(x→ep₁) and e(xde) (Figure 5). According to J(P_m) and the sub bounds of J(P_m) are 4-3CP: J(p₁-p₂), J(p₂-p₃), ···, J(p_n-1-p_n) and J(x→p_n), J(p₁→x) and J(x→p_nd), J(x→ep₁), e(xde) are 3CP. According to 4-3CP Conjecture, when x scans on P_n (x ≠ p₁, p_n), the colouring solution set family Y(P_n) (Y(P_n) ∈ Y) must have a 3-colouring solution set 3Y(P_n) make J(p₁-p₂), J(p₂-p₃), ···, J(p_n-1-p_n) and J(x→p_nd), J(x→ep₁), e(xde) are 3CP. If y(a) = y(x), 3Y(P_n) will make |Y(J(a + P_n))| = 3 and make J(a→p_nd), J(a→ep₁) and J(p₁-p₂), J(p₂-p₃), ···, J(p_n-1-p_n) are 3CP, which means {J(a + P_n)} are 3CP. So, ∃ a 3-colouring solution set 3Y(J(a + P_n)) make {J(a + P_n)} be 3CP. 4-3CP Conjecture (4) is proven.

Figure 7 Figure 5.

Figure 8 Figure 6: a E 3-colour sub-bound of J(a + P_m), a = x.

When The New Point A ∉3-Colour Sub-Bound Of J(A + P_m)

Since point a ∉ 3-colour sub-bound of J(a + P_m), we shall to prove all sub-bound J(a + P_m’) with point a are AP.Take any n + 2 points P_n = {d, e, p₁, p₂, p₃, ···, p_n} ⊆ P_m, link e-p₁, p₁-p₂, p₂-p₃, ···, p_n-1-p_n, p_n-d, form (n + 2) sub-bounds J(p₁-p₂), J(e-p₁), J(p₂-p₃), ···, J(p_n-1-p_n), J(p_n-d) and J(a + P_n). (Figure 6) According to the boundary J(P_m) and the sub bounds of J(P_m) are 3CP: J(P_n), J(e-p₁), J(p₁-p₂), J(p₂-p₃), ···, J(p_n-1-p_n), J(p_n-d) are 3CP, ∃ 3-colouring solution set 3Y(J(P_n)) ∈ Y, make {J(P_n)} be 3CP. According to the Points Scanning Method: If y(a) ∉ 3Y(J(P_n)) and y(a) ∈ Y, J(a + P_n) is AP, so all sub-bound J(a + P_m’) with point a are AP. Sum up 5.1.1, 5.1.2, we can see 4-3CP Conjecture (3) is proven.

Proof of 4-3CP Conjecture (5)

Set Pm’ ⊆ Pm, Pm’ divide J(m) into m’ parts, let x is a point between p₁→p₂ (x ≠ p₁, p₂) on J(m), we call p₁, p₂ are fixed points, x is scanning point. Link x-p₁, x-p₂, ···, x-pm’, form a sub-bounds set {Ji(x) | x ∈ Ji(x), i=1, 2, ···, m’} of J(m). (assume m’ = 5, see Figure 7). According to 4-3CP Conjecture (5), when x scans on p₁→p₂, ∃ 3Y(J1+ J₂), and

J₃, ···, J_m’, J_m’+1 are 3CP. Then add a new point a on J(m), when point a is on J₁, J₂, ∃ y(a) ∈ Y(J₁(x) + J₂(x)), keep |Y(J₁(x) + J₂(x))| = 3, and J₃, ···, J_m’, J_m’₊₁ are 3CP; when point a is on J₃, ···, J_m’, J_m’+1, ∃ y(a) ∈ Y, keep J₃, ···, J_m’, J_m’₊₁ are 3CP; when point a is a fixed point as p₁, p₂, we also could prove that, when x scans on p₁→p₂, ∃ 3Y(J₁+ J₂), and J₃, ···, J_m’, J_m’₊₁ are 3CP (we will prove in detail in next article), so J(m + a) can keep when x scans on p₁→p₂, ∃ 3Y(J₁+ J₂), and J₃, ···, J_m’, J_m’₊₁ are 3CP. So 4-3CP Conjecture (5) is proven (Figure 8).

Figure 9 Figure 7: a ∉ 3-colour sub-bound of J(a + P_m).

Figure 10 Figure 8: Sub-bounds set {J_i(x) | x ∈ J_i(x), J_i(x) ∈ J₁, ···, J₆} of J(m).

So Y(a + m) can make:

The bound J(a + m) be 3CP,

∀ sub-bounds set {J’(a + m)} be 3CP,

∃ a 3-colour solution set 3Y(J’(a + m)), and

be 3CP.

Let x, p₁, p₂ ∈ J’(a+m), link x-p₁, x-p₂ form sub-bounds J’₁(x-p₁), J’₂(x-p₂),

, if x scans on p₁→p₂, ∃ 3Y(J’₁+ J’₂) and

is 3CP. Above all, we have proven 4-3CP Invariance during the Expanded Operation e(+, p_i), It’s easy to see 4-3CP Invariance during the Expanded Operation e(-, p_i) is also true. So 4-3CP Conjecture is proven!

Conclusion

The major research objects are the boundary’s invariance property of Standard Graph in this work. By creating the Standard Graph via Expanded Operations e(+, p_i) and e(-, p_i), the complexity of the planar graph is reduced. By examining the Invariance during Expanded Operations (IEO) of Standard Graph, huge calculation for coloring planar graph are avoided. Based on the above optimization method, we have demonstrated a rigorous proof of the 4-Colour Theorem, which can be also used to optimize complex systems.