Navigation: Home > The four-colour map problem

The four-colour map problem
These are my own ideas on the four-colour map problem. They are laid out in the order in which they developed to show my train of thought. I describe two alternative methods of colouring a map, using only four colours. Hopefully all will become clear as you read through this topic.

1. Definition of the problem

Take a map, of any complexity, which is divided into several regions such as countries, states or counties etc. Is it possible to draw the map using a maximum of four colours such that no two adjacent regions, sharing a border, have the same colour? I begin by stating the rules of the game.

2. Rules

Certain rules are required to make the problem meaningful.


Rule 1. Two regions sharing the same border cannot have the same colour.
Rule 2. Several regions meeting at a point, or node, can have the same colour as long as Rule 1. is obeyed.
If Rule 2. did not apply, eight regions meeting at a node would require eight different colours, and we would not be considering the problem.

3. Practical map making

Things are not always simple when making a real map. For example, if the map is to include the sea as well as the land, the sea has to have a unique colour - usually pale blue.
Consider the case of a continent, consisting of four countries, surrounded by the  sea.
In this case the map requires five colours to satisfy Rules 1 and 2 and for the sea to be a unique colour.

The Four-colour Map Problem as is it usually posed does not allow for such exceptions, so a third rule is required:

Rule 3. All regions must have equal status.

4. Nodes

In the next section we will look at small areas of a map and determine the least number of colours that are required to satisfy the rules for each type of structure.

Regions adjacent at a node
A node is a point where several regions meet.
 
A node, where an odd-number of regions meet
(An odd node)

These arrangements require no more than three colours.

A greater odd-number of regions will not increase the number of colours required.
An odd node where one region touches the node more than once.

Here the yellow region touches the node more than once with one, or more, intermediate regions.

No more than three colours are required.
A node, where an even-number of regions meet
(An even node)

These arrangements require no more than two colours.

A greater even-number of regions will not increase the number of colours required.
An even node where one region touches the node more than once.

Here red region touches the node more than once with one, or more, intermediate regions.

No more than three colours are required.

Replace the node with an extra region and you will see that one region surrounded by any number of adjecent regions requires no more than four colours.

5. Adding a new region to an existing map

Here the method is to try to construct a map of any complexity starting with a simple map, or even a blank map, and adding regions one at a time.

Simple case
Shown below are all the ways in which a new region can be added to a structure consisting of a region surrounded by three adjacent regions. The same principles apply to a structure consisting of a region surrounded by a greater number of adjacent regions.
 


1. Start with a structure requiring four colours,
2. Adding a new region, contained completely within an existing region, requires no new colours.
3. Extending the new region, across a border to a second existing region, requires no new colours.


4. Extending the new region, across a node into a third region, requires no new colours.
5. Extending the new region, up to a second node, means that the first and second regions no longer share a border.
6. Only three colours are now required.


7. Extending the new region across the second node results in two regions, of the same colour, sharing a border.
8. The colour of the new region has to be changed. Four colours are now required.
9. Extending the new region across the final node returns the structure to the original configuration.
The crucial Action
The crucial action is when the new region is extended up to and across the second node (Steps 5 to 8).The second region becomes separated from the first region immediately before the new region becomes adjacent to the third region. Thus, by this action, no more colours are required.
Complex case
What about a more complex map? Building upon the principle of the Crucial Action established for the simple case, we find there are two possible scenarios. Scenario 1. where regions, either side of the new region, are not part of a loop, and Scenario 2. where they are part of a loop.
 




Scenario 1.
1. Here is a map using only four colours. The green and blue regions, 1 and 2, are adjacent.
2. A new region is added, between 1 and 2, surrounded by four different coloured regions. The colour of one of them must be changed.
3. Reverse the colours of all the adjacent green and blue regions to the right of the new region.



4. There are now only three different colours surrounding the new region, which can be coloured blue.
The new map only requires four colours.
Scenario 2.
1. Start with a similar map, but here the adjacent green and blue regions are part of a loop.
2. Again, a new region is added, between 1 and 2, surrounded by four different coloured regions. The colour of one of them must be changed.



3. Reversing the colours of adjacent green and blue regions, to the right, still results in four colours surrounding the new region, because of the loop.
4. Change the colour of the adjacent yellow region, above, to red.
5. There are now only three different colours surrounding the new region, which can be coloured yellow.
The new map only requires four colours.

6. Strings

The investigation of the principle of 'Crucial Action' leads to the idea of strings.
Any map consisting of four colours can be divided into 'strings' of regions, each of two colours.

This is a simple string (a spur) consisting of red and yellow regions.
The colours in a string can be reversed without changes being required in the rest of the map. I call this 'Colour Reversal in String' or CRIS.
A string may be branched.
A string may take the form of a loop.

A loop must consist of an even number of regions.
A string may take the form of an array. An array can be thought of as a thick version of a spur.

An array must contain only even nodes, within itself.
A string may consist of all of the above forms.
String properties
The following properties refer to a four-colour map coloured in red, yellow, green and blue.

Property 1.
In a four colour map there are six possible string configurations:
Red/yellow, red/green, red/blue, yellow/green, yellow/blue and green/blue.

Property 2.
Strings come in complementary pairs:
Red/yellow with green/blue, red/green with yellow/blue and red/blue with yellow/green.

Property 3.
The colours in a string can be reversed without changes being required in the rest of the map, (CRIS).

Property 4.
A string cannot contain odd nodes.

Property 5.
A string can contain even nodes.

Property 6.
The end of a string can be terminated by the edge of the map, by a node, or by its complementary string.

7. Adding a new region to a string
Add a new region to a spur.
The new region can be incorporated into the spur by colouring it one of the existing spur colours, in this case red, and applying CRIS to all the regions to one side, in this case to the right.

This can be done without breaking any of the rules as the spur is completely surrounded by other coloured regions, e.g. green and/or blue regions.
Try to add a new region into a loop. Reversing colours will not work. The new region can be neither red nor yellow.
To maintain a map consisting of just four colours the new region has to be part of another, complementary, string.
Loops cannot intersect. The second string can only enter, what was the first loop, as a spur. So, in the previous diagram, the part of second string which contains the new region cannot be a loop. This is why the new region can be added to the second string without needing an extra colour.
A new region surrounded by four regions - four colours
The above examples dealt with a new region surrounded by four regions, all differently coloured .
Let's continue looking at this configuration.
The new region cannot be part of the red/green string because the red/green adjacent pair creates an odd node, with the new region. This requires three colours.

The same applies to the yellow/green the yellow/blue string and the red/blue string.
This leaves the red/yellow and the green/blue strings as possible homes for the new region.

As they are complementary strings, at most, only one of them can be a loop. So, the CRIS principle can be used to colour the new region without using more than four colours. In this case yellow, in the red/yellow string.
So a new region can always be inserted, in a position where it is initially surrounded by four different coloured regions, without using more colours.

What about a new region surrounded by more regions?
A new region surrounded by five regions - four colours
The new region cannot be part of the yellow/blue string because the yellow/blue adjacent pair creates an odd node with the new region. The same applies to the red/blue string, the yellow/green string and the green/blue string.
This leaves only the red/yellow and the red/green strings as possible homes for the new region. In this case colour it red, in the red/yellow string.
In this map, with the same configuration around the new region as the previous one, Adding the new region to the red/yellow string would form a loop with an odd number of regions - not allowed.

 The red/green string looks a possibility.
Making the new region red, and reversing the red/green string colours to the right, seems to work.
But there is a problem if the new region then became part of an odd loop in the red/green string. The red/yellow loop cannot block an odd loop in the red/green string as it could in its complementary green/blue string.

However, the colour of one of the regions in the new loop can be changed. For example the red one at the top.
This region can be part of two other strings - red/yellow and red/blue.
Use CRIS to swap its colour, in this case to yellow.

The colours of the red and green regions to the right of the new region can also be swapped, and the new region coloured red.
A new region surrounded by all possible adjacent pairs
With four colours, there are six possible adjacent pairs. It turns out that to arrange them around a new region requires eight surrounding regions (Two pairs are duplicated)
There appears to be no string available for the new region to join.

Does this mean you need more than four colours to colour some maps?

The answer is 'No', but I will deal with this situation in Section 10.

8. Another way

Is there another way of avoiding this problem?. Up till now my ideas have developed along the lines of adding new regions to a map. I have learnt a lot in the process, in particular about strings. Having got that experience, what about doing what most people would have tried in the first place - colouring an existing map from scratch?

Solution 1.
Rather than add regions to an existing map, colour a map with all the regions already in place.

Solution 2.
The problem was caused by loops. Why not try to avoid loops altogether?
Avoid loops by colouring the strings so that at least one end of each string terminates either (at the edge of the map) OR (at a node where other like strings meet AND where at least one end of one of these strings terminates at the edge of the map.)
Example:
These three like strings satisfy Solution 2, and cannot be enclosed by a loop.
Colouring a map
Colour an existing map one string at a time.
This map contains odd and even nodes of various values, and regions surrounded by odd and even numbers of other regions.
Starting at the LH edge of the map, colour a string (red/yellow) along the bottom edge.
Then, colour the next adjacent complementary string, (green/blue).
Starting at the LH edge of the map, colour the next red/yellow string. This string cannot continue after the second red region.
Colour the next green/blue string. It becomes a branch of the previous green/blue string.
Colour the next red/yellow string.

Leave, for now, the potentially difficult region which is surrounded by four differently coloured regions.
Colour the last green/blue string.

 Return to the potentially difficult region left blank earlier. It cannot be part of the following strings as it meets them at an odd node: Red/yellow, yellow/green, green/blue, or red/blue.

 This leaves either the red/green or yellow/blue strings as the home of this region.
For example, colour it yellow and reverse the colour of the rest of the yellow/blue string to its right.
Colouring procedures
There are three additional procedures I have used when colouring this map.

Procedure 1.
Colour the map one string at a time.

 Procedure 2.
 Colour adjacent strings sequentially.

 Procedure 3.
 Leave any potentially difficult regions till last and deal with them using the CRIS principle.

9. The strings within the map

Obviously, if the map is coloured successfully using one pair of strings, all the other string combinations are present too. Here are the complementary strings from the previous map.
The red/yellow strings and green/blue strings.

The red/green strings and yellow/blue strings.
The red/blue strings and yellow/green strings.
This just leaves the outstanding issue of a new region surrounded by all possible adjacent pairs.

10. A new region surrounded by all possible adjacent pairs
There appears to be no string available for the new region to join.

 The problem can be tackled in two ways.
1. The problem should never arise if, when colouring the map, adjacent strings are coloured, sequentially.

This configuration only requires three strings. The red/yellow string along the bottom edge, the green/blue string above it and the next red/yellow string above that.
2. Even if we did find ourselves in this situation. For example, because the new region is a potentially difficult region we left till last, there is a solution.

Because there are no potential loops in the map, each of the non-adjacent surrounding regions is the end of a different string.
Here, we show the strings connected to the two yellow surrounding regions.
We can reverse the colours of these two strings, and the new region can be coloured yellow
That just about wraps it up.

11. Conclusion

I have described two alternative methods for colouring a map using only four colours.
  1. Obey the three Rules, remember the six String Properties and use CRIS to overcome  potential loop problems.
  2. Obey the three Rules, remember the six String Properties, use the two Problem Solutions and follow the three Colouring Procedures.
What I need now is help to see if these ideas can be brought together in a formal proof.

Mike Holden - Jan 2009
Navigation: Home > The four-colour map problem