A proof of the four color theorem?   (Draft only)

The colored graphs on the margin show not the full set but only a subset of all possible solutions how to use 4 colors to color each region of a given graph differently from any neighbouring region (4c-solutions). The type of subset shown I call a heureka set.

Definition of a heureka set: A heureka set you find by starting from a given four color solution S1 for a given graph. You choose one region and call it CR (central region) .  You choose a neighbouring region and call it SR (solid region). You find more members of the heureka set by the heureka transformation that leaves the color of SR (i.e. blue) and of all other regions with the same color unchanged. The color of CR is changed by rotation between three values (i.e.  green, red and yellow). By changing the color of CR for instance from red to green you force all neighbours of CR formerly green to take the colour red. In a cascade way possibly more regions are forced to change their color between red and green and you reach an additional 4c-solution).

Apply to the four color problem: Given a graph with a 4c-solution. A new line subdividing a region named DR (region to be divided) is introduced. How do you find a 4c-solution for the new and more complex graph? Usually the line newly introduced starts and ends on the border lines between XR and DR and between YR and DR. In the original graph you name XR as CR (XR=CR). DR you name SR (DR=SR). Now, as you have named CR and SR you can find a complete Heureka Set. Within this Heureka Set with certainty* you find a suitable 4c-solution that easily can be transferred to the new and more complex graph. Suitable solutions are the ones, where you can travel from XR ,i.e. green or red, to YR ,i.e. again green or red, without crossing a region not green or red.

© eureka@4colprob.com                                          Sign GuestBook

* I must put a question mark here!                                   

How do you find a Four Color Solution (if existing*) for any given planar cubic graph?

The following strategy always provides a solution:

Step 1,  tag each node with the value 3 or 6

Step 2,  choose one edge as the “fuxian home”. Choose a direction for the fux to start it’s moves and choose it’s initial mood  (one of two values, either criss or cross).

Step 3 ,4,5...etc. : Let the fux move over the facing node onto a nearby edge. The direction of the move is decided by the mood of the fux and by the label value of the node. The node value 3 or 1 signify “turn right”, the value 6 or 2 mean ”turn left”.  When  in “criss” mode the fux will comply, when in “cross” mode the fux will choose the opposite direction. After each move the fux changes it’s mood and is ready for the next move over the next node onto the next edge. Any node that has been passed over  by the last move changes it label value. If it was 3 it changes to 1, if it was 6 it changes to 2. If it was 2 it changes to 1, if it was 1 it changes to 2.

On it’s way the fux  removes all label values of 6 or 3. Once  this has happened and the fux has returned to the fuxian home a four color solution has been created. You only need to replace all nodes tagged with the value 2 by a small triangle, and you find that all areas now are bordered by a number of edges divisible by 3. According to Heawood , you now find a 4c solution.

 * Not all planar cubic graphs are 4-colorable!