Four color theorem

The Four color theorem is the challenge to draw first a map consisting of different 'countries' and then to color the different countries with a minimum number of colors. The minimal number is 4.
The line between each country is called a boundary. There is one constrain involved.
  1. The constrain is that the maximum number of countries involved at each point on the boundary is three. This meant there can be no point where 4 countries meet.
For more detail select: For the source of the program select:
This zip file consists of two copies of the program:
  1. Four_color_theorem.xls This program is the real program and contains 10 simulations.
  2. Four_color_theorem_test.xls This is the same as above, but is more meant to try your own examples.
There is also a painting by the author, which demonstrates the 4 color Theorem. To see the painting select: 4 Color theorem
For further reading select: "Formal Proof—The Four Color Theorem" by Georges Gonthier

Page description and operation

Each Page or Blad consits of 3 parts: A left part, a center part and a right part.

Picture 1

Parameters of the program

The program uses 5 parameters: cnt, lvl, Err, Sol and Max The 5 parameter display area also contains 3 additional parameters:

The right side of the display.

The right side shows the results of each simulation and is subdivided in 4 sections.
Section 1 consists of 2 columns. Section 2 of 4. Section 3 of 4 and Section 4 of 1.

Program Four_color_theorem.xls

The Program Four_color_theorem.xls contains 10 simulations.
The first time user is adviced to select each simulation in succession and not to perform any calculation. Generally speaking the higher examples are the most difficult.
When you observe the results you will see that below each result a field marked "Err". The number behind that field identifies the number of errors detected.
In Blad1 the values is 0. In Blad2: 0. In Blad3: 0. In Blad4 0: In Blad5: 0. In Blad6: 0. In Blad7: 1. In Blad8: 8 and in Blad9: 14.
When you study Blad7, Blad8 and Blad9 you can easily see that there is an increase in complexity.

When you are finished you can select the "calculate" button for each simulation. Keep the mode "Auto". When the simulation is finished select the End Command button. Specific observe the lvl parameter and the END of each simulation.
In Blad1 the value lvl parameter is 1. In Blad2: 1. In Blad3: 2. In Blad4 3: In Blad5: 6. In Blad6: 6. In Blad7: 4. In Blad8: 4 and in Blad9: 14.

What follows is a short description of each simulation or "Blad"

  1. "Blad1" is very easy. The parameter lvl is 1 and # of errors 0
  2. "Blad2" is also easy. The parameter lvl is 1 and # of errors 0
  3. "Blad3" is shown in Picture 1. The parameter lvl is 2 and # of errors 0
  4. "Blad4" the parameter lvl is 3 and # of errors 0
  5. "Blad5" demonstrates the top part of the "4 Color theorem" painting. The tail and legs are not included. The simulation shows 36 countries.
    The parameter lvl is 6 and # of errors 0
  6. "Blad6" demonstrates the bottom part of the "4 Color theorem" painting. The tail and legs are not included. The simulation shows 37 countries.
    The difference between "Blad5" and "Blad6" is in country number 17, which is divided in two (Country #17 and country #37). This only difference has a large influence. The more or less 15 countries in the center are the same. The other countries have different colors. The parameter lvl is 6 and # of errors 0
  7. "Blad7" Shows a rather simple example. In the center there is one green country with the number 3. It is possible to make this country blue with the number 4. That means the inner part of 12 countries has only the numbers 1,2 and 4. It is easy to see that you can copy this country and make the inner part twice as large, only with three colors. etc etc.
  8. "Blad8" is the same as "Blad7" with only one country added.
    The parameter lvl is 4 and # of errors 5
  9. "Blad9" is the same as "Blad8" with more or less the inner part of "Blad7" copied.
    The parameter lvl is 11 and # of errors 15
    See also "Blad9" of paragraph Four_color_theorem_test.xls
  10. "Blad10" is the same as "Blad9" with only one country missing. See also paragraph Four_color_theorem.xls Blad9 and Blad 10 .

Program Four_color_theorem_test.xls

The program Four_color_theorem_test.xls also contains 10 simulations.
In the program Four_color_theorem.xls each simulation always shows two maps: The "Target map" and the "Result map".
The Four_color_theorem_test.xls program sometimes contains a third map called the "User map".
The "User map" is a copy of the original "Target map" as original build, including some errors.
When you want to perform any simulation which also contains a "User map" you should first check that the "Target map" is the same as the "User map". When that is not the case you should copy the "User map" onto the "Target map".
To get an impression about each simulate use the "Auto" mode.

What follows is a short description of each simulation or "Blad"

  1. "Blad1" contains a "User map" and is used to demonstrate a situation where four countries meet each other at one point. There are two of these situations. The demonstration also shows a third situation where four countries meet, when two countries have the same number.
    The user should perform a simulation (Select Calulate) and observe the three errors. Next to make the necessary modifications in the "Target map" and try again.
  2. "Blad2" is used to demonstrate the simulation discussed in
  3. "Blad3"
  4. "Blad4" is used what happens if not all the countries are created. For example country #1 is missing.
  5. "Blad5" Is used to simulate that it is only required to indicate the outer corners of each simulation. Most of the empty numbers are filled in automatically. b>"Blad5" is also used to demonstrate 1 small error. It is difficult to find by visual inspection. Try it.
    Otherwise select "calculate".
  6. "Blad6"
  7. "Blad7"
  8. "Blad8"
  9. "Blad9"
  10. "Blad10" Shows an example of the 50 states of the USA. 2 states are not shown. The parameter lvl is 13 and # of errors 2

Four_color_theorem.xls Blad9 and Blad 10

When you don't select Picture 2 the image shows 32 countries of Blad9 of the program Four_color_theorem.xls. The number of levels is 11 and the number of errors is 15 that means it is an easy configuration.
The purpose of this particular example is to demonstrate what happens if one country is deleted.
You will see that when you select picture 2.
31 versus 32
Picture 2
When picture 2 is selected the image shows 31 countries of Blad10 of the program Four_color_theorem.xls. The number of errors has increased to 41835. The only difference is in country #25 of Blad9. This country is missing in Blad10. This only one difference is quite amazing because to perform the simulation takes very long.
The main reason for this change in performance is country #9. The color has to be red. Country #9 is the country right above the yellow country in the center.
When you look carefull you can also see that there is a solution with only the outer border (Country #15) is blue.

Excel Program description

The excel program more or less consists of two parts.
                Exit sub
                ' one choice
                Exit sub
                ' two choices
                     Error --> Exit

The three most important subroutines are Maximum1, Maximum2 and Maximum3.
  • Subroutine Maximum1 calculates the first three countries.
  • Subroutine Maximum2 is a recursive subroutine.
    This subroutine first calls the subroutine Process. Next it selects countries based on two criteria:
    • When there is only one choice the country is selected and Maximum2 terminates
    • When there are two choices we have what is called a fork. One country is selected and the subroutine Maximum2 is called again.
    When these criteria are not enough it calls the sub Maximum3.
  • Subroutine Maximum3 is called to make a more complex choice between which country has to be selected.
  • Subroutine Process selects colors using the subroutines Test_kleur and Test_kleur2
  • Subroutine Test_kleur tests if only one color is possible.
    The subroutine tests of each country the colors of each surrounding country. When the number of colors of the surrounding countries is three then the color of the tested country is #4.
  • Subroutine Test_kleur2 tests if only one color is possible.
    The subroutine tests of each country the colors of each surrounding country and the number of countries that have no color. When the number of colors of the surrounding countries is two and the number of free countries is 0 or 1 then color of the tested country can be anyone of the two not used colors.

Reflection part 1 - prove

The first purpose of the simulation is to demonstrate that it is possible to color each combination of countries under the rule that nowhere there should be any point where 4 countries meet.
The second purpose is to prove that this is possible. The point is that you can never test each and every combination. In reality only a limited one. The question which minimal set of countries is sufficient as a prove that the 4 color theorem is valid for all combinations.

You can also use the same concept as raised by the following question: How do you prove that a perpetual motion machine does not work? Built one.
Until now all the simulations that did not work are caused by programming errors.
At 15 december 2018 a programming conceptual error was discovered in the subroutine process. The subroutine first calls Test_kleur and secondly Test_kleur2
In principle after making this second call the first subroutine should be called again. Now the two are called in a loop until no change is detected.
At 15 december 2018 also a programming error was detected in subroutine test_kleur2. The structure setup was not correct for the last country tested. The structure was changed.

Reflection part 2



Created: 12 April 2018

Back to my home page Contents of This Document