The human proof and algorithm for Four-Color Theorem
This paper presents a simple human proof of the Narrow Four-Color Theorem “Given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color, and all the outermost countries use no more than three colors. (Please refer to “Concept” for the meaning of “outermost countries”)”. And in this proof also shows the algorithm for Four-Color Maps. This paper is from a new way, from first principle (the basic and simple facts) to the final result.
Concept
Outermost countries
countries adjacent to the infinite plane (refer to below photo, the countries highlight in yellow color)
The Map
means the Map that all countries in one continent.
I will prove situation for only one continent map in the paper. For the separate continents, if the theorem holds, for each continent, the theorem also holds, we can let 4 the colors of outermost countries for each continent to be same, so the theorem still holds. (Refer to below photo.)
The symbol and convention
Map(X): Represent maps of X countries
The four colors: A, B, C, D
M: The number of outermost countries in the map.
NMM: The number of all outermost countries adjacent to an outermost countries.(Refer to below photo)
The Fact
Fact-1: For any map, have at least one outermost country.
Fact-2A: Any 4 outermost countries, cannot adjacent with all of each other. (If all of them adjacent with all of each other, will like below photo, it’s contradicts with that these 4 countries are outermost countries. )
Fact-2B: Any 4 outermost countries, at least two countries not adjacent to each other. (Fact-2A, implies Fact-2B)
Fact-3: For any map, the minimum of NMM is no more than 2. (Refer to below photo)
Fact-4: If there are two countries adjacent, we can set color for them, for example one is P, another is Q, we can set A for P, we can set any color in (B,C, D) for Q, it won’t affect the result. Because any two adjacent need to use different colors.
(The result meaning: If “the map can use only four colors, and all the outermost countries use no more than three colors” is true, I set color for P and Q, the result still true. If “the map can use only four colors, and all the outermost countries use no more than three colors” is false, I set color for P and Q, the result still false. )
The Proof Idea
The keypoint of this proof: I can color the "shell" of a map (outermost edges) with only 3 colors. Then I can proceed by induction by removing one node from the shell, recoloring with a 3 color shell, and re-attaching node.
According to Fact-1: I can Classification all maps from the number of its outmost countries (the “M”) into: M=1, 2, 3, 4 and M>4.
For M>4, according Fact-3, I will further classification the maps from the number of NMM into 0, 1, 2.
When I handle M>4 and NMM=2, I will use the principle of Fact-4.
The principle of Fact-2A and Fact-2B is used in all classification.
Comments
Post a Comment