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! |