The four-colour mapping theorem states that all maps can be four-coloured (adjacent regions receive distinct colours, and four different colours are used in total). However, the technical definition of "map" implies that regions must be contiguous, and, in fact, it's easy to construct counter-examples to a proposed "four-colour not-necessarily-contiguous-mapping conjecture". For example:

alt text

where the two green areas constitute a single non-contiguous region. This is clearly not four-colourable since each of the five internal regions is adjacent to every other (forming a $K_5$ in the graph-theoretic sense).

Some real-world maps have disjoint components (e.g. USA, including Alaska, Hawaii), which leads me to:

Question: What is an example of a real-world map (which necessarily must have at least one non-contiguous region) that is not four-colourable?

  • 8
    $\begingroup$ There are other conditions in a real world map that may prevent 4-colorability, like regions meeting at a point (e.g., Colorado, Utah, New Mexico, and Arizona meet in a "corner", as do Chad, Niger, Nigeria, and Cameroon; if they were all "inside" another country, you would also end up needing 5 colors; or if you had 5 "slices" meeting at a corner) $\endgroup$ – Arturo Magidin Jan 3 '11 at 23:48
  • $\begingroup$ Indeed I did miss that (rather important) condition. Although, hopefully the meaning of the question is not lost as a result. $\endgroup$ – Douglas S. Stones Jan 4 '11 at 0:38
  • 1
    $\begingroup$ So here is a general problem: You have a map on the sphere. The set of countries is partitioned into nonempty blocks. Two countries in the same block do not touch each other. Color the blocks such that adjacent countries get different colors. How many colors will suffice? $\endgroup$ – Christian Blatter Jan 5 '11 at 14:13
  • $\begingroup$ What evidence is there that anyone imposed a condition that regions meeting at a point needed different colours? Right from the earliest days of when the four-colour problem was considered, no such condition was imposed -- it is obvious that, if it were, there would not be any finite bound to the number of colours needed, because any number of regions can meet at a point. $\endgroup$ – Rosie F Mar 29 at 8:30

Wikipedia has a list of sets of four countries that border one another; it includes a few divided countries (Russia, in Belarus-Lithuania-Russia-Poland, with Kaliningrad being separated from the rest of Russia; and Azerbaijan in Azerbaijan-Iran-Armenia-Turkey). There do not seem to be any set of 5 or more currently.

Added: However, one could argue that the existence of disconnected countries in fact forces certain maps to use more colors, even though they do not involve disconnected countries. For example, a map of Europe would necessarily require different colors for France, Belgium, the Netherlands, Germany, Denmark, Norway, and the United Kingdom (possibly also Ireland), lest it seem that one of those countries is disconnected into two non-adjacent regions. This also shows some of the difficulties that islands produce (as opposed to the idealized maps from the theorem).

There was a time when Britain, Spain, France, Portugal, and the Dutch Republic bordered each other (early 18th century, counting borders lying between colonies); and from the late 19th century until before World War I, so did Belgium, Portugal, Germany, France, the United Kingdom, and the Netherlands (necessitating six colors; again, this includes colonies that may border one another).

It's possible that some smaller divisions (states, provinces, etc.) might include such sets.

As I noted in the comment, there is an incorrect assumption in your question that a counterexample must have disconnected regions: in the four-color map theorem it is assumed that neighboring regions have a border of positive measure. Countries/states meeting at a point (such as Colorado, Utah, New Mexico, and Arizona meeting at the Four State Corner) are required to use different colors in maps, but in the context of the 4-color map theorem regions that only meet at the point could be colored using the same color.

  • 3
    $\begingroup$ That Wikipedia page is just amazing :) $\endgroup$ – Mariano Suárez-Álvarez Jan 4 '11 at 1:41
  • 3
    $\begingroup$ If you add a 5th "country" called "sea" and which is always colored in blue, you can expand some of the 4-countries-set on the wikipedia page to 5-"countries"-set $\endgroup$ – Frédéric Grosshans Jan 4 '11 at 10:44

Here's a map of the Holy Roman Empire after the Peace of Westphalia in 1648.

In the color scheme the map makers have chosen, the pieces of the map labeled "Bavaria" (green), "Austrian Hapsburg" (light green), "Ecclesiastical" (light purple), "Hohenzollern Franconian" (light brown, including Ansbach and Bayreuth), and "Imperial Cities" (red) all touch each other. So five colors are required to differentiate them.

  • $\begingroup$ Imperial Cities are not a single entity. $\endgroup$ – Louis Rhys Jan 4 '11 at 7:11
  • 1
    $\begingroup$ @Louis: Right. However, the map makers clearly wanted to use a single color for all the imperial cities. And that makes sense, as they shared something fundamental with each other that they did not with the rest of the Holy Roman Empire in 1648. This is not any different than using blue to color both the Atlantic and Pacific Oceans; those are different entities as well, but they share something fundamental with each other that they do not with the land regions on the globe. With this restriction, you do need five colors. $\endgroup$ – Mike Spivey Jan 4 '11 at 17:19
  • $\begingroup$ Talk about crumpling. $\endgroup$ – Joe Z. Feb 15 '13 at 21:35

Google "colonial Africa". The Belgian, French, German, British, and Portugese colonial areas are all adjacent. The only difficult-to-spot adjacency here is Portuguese-French, which is taken care of by Cabinda and French Equatorial Africa. (This map actually only requires five colors, because the Italian, Belgian, and Spanish colonies are all non-contiguous, and Ethiopia is not contiguous to a German colony).


Georgia, Armenia, Azerbaijan, Turkey, Iran, Turkmenistan, Kazakhstan, Russia.

First, make $K_5$ using G, Ar, Az, Turkey, I. (Turkey borders Azerbaijan's Nakhichevan region.) Then subdivide G~I into the path G~R~K~Turkmen~I. This means that the graph of borders of the aforementioned 8 countries is homeomorphic to $K_5$ and is thus not planar.

  • $\begingroup$ It's not planar, but the subgraph you've described is certainly 4-colorable. $\endgroup$ – Misha Lavrov Mar 29 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.