Cecil’s Column on the four-color map problem.
Note that the column was written in 1984, and that the research in question dates to 1976. The column begs two simple questions:
Is the four-color map problem still solved, considering that the nations of the world have sub-divided and rearranged a few times since 1976?
Considering the advances in computing made since then, does the problem still require a mind-boggling degree of computing power, or can it be done today on a home PC?
TIA
As to (1) I believe that the problem relates to any conceivable map, not to the map of the world.
How the heck could that be? Just using a map of the USA I could find a few places where any state is contiguous with 4 other states.
Let’s say we use red, blue, green, yellow.
Virginia is yellow.
Maryland is blue.
West Virginia is red.
Kentucky is green.
What do we use for Washington DC, North Carolina, and Tennessee?
It’s a question of theoretical maps, not real ones. In fact, in the real world, the proof won’t necessarily work, because some countries are in more than one piece.
Yes, any decent home PC could do the job now.
Cecil’s statement of how it was done is a little brief, and a little misleading. Around 100 years ago, someone announced a “proof”, but, a little later, someone pointed out one little flaw where the “proof” broke down. The “proof” was reworked into a solid proof that five colors were sufficient (and any idiot can prove that four colors are sometimes necessary), and, for many decades, that was how the problem stood, stuck between four and five.
Haken and Appel investigated the hole in the “proof,” and saw a possibility that the number of ways it could go wrong was finite. They used a computer to make a list of all the possible ways; it was something like a thousand. Then they looked at the first case, and discovered a proof that, although the original “proof” didn’t work for it, four colors were still good enough. So they instructed the computer on how they had done it, and had it go through all the other cases. For each one, they, or the computer, could prove that, although it was an exception to the original “proof”, it wasn’t an exception to the four-color rule.
So the original flawed “proof”, plus their something-like-a-thousand mini-proofs to fix the flaw, make one good proof. On a plane, or on the surface of a sphere (the two problems are equivalent), there is no possible arrangement of one-piece “countries” that cannot be colored with only four colors.
(On the outside of a doughnut, for what it’s worth, seven are needed.)
I’m still not getting it. If it’s easily demonstrated that the proof is incorrect in the real world then why go to all the trouble of constructing a proof.
Maybe I need a background in why and how this was done. Anyone sum up the circumstances, whys and wherefores in 200 words?
DC is green
NC would be Yellow
TN red
The point is that you can not have more then four contigus shapes, ie not broken, at more then a point where all would touch. You can make a US map with only four colors and it does work, it’s a pain but it does work. However, us cartographers are just a bit smarter and use five to six colors so we don’t have this problem.
Is this dependent on being on the suface of a sphere? I ask because it seems fairly easy to come up with something that breaks the rule if you only use a sheet of paper, i.e 2D.
I can’t draw it here but if you want to see it, send me an email.
The proof is not incorrect in the real world, but it’s not applicable to real-world maps because a country could be in two separate regions (e.g. US is 48 contiguous states + Alaska and Hawaii) and depending on how the separate regions are arranged you might need more than four colours for a political map.
Why bother proving that a four colours suffice for a map on a plane or sphere? Because any piece of knowledge in mathematics can have unexpected practical applications, and/or lead to new avenues of research.
That’s not flying. In the scenario described both Virginia and North Carolina would be yellow.
What I’m saying is that it’s possible to define on ANY plane of sphere a series of shapes that have more than 3 contiguous other shapes. And I see that as invalidating the ‘proof’ here.
I’m freely willing to admit that I’m missing something. But what that is I’m not getting.
Maybe I’m missing something here… but I’m still confused as to just how many colors, MINIMUM, are required to draw a map so that no two same-color areas are touching…
…is it four or five?
JonathanChance: Virginia Yellow
Maryland Blue
West Virginia Red
Kentucky Blue
Washington, DC Green
North Carolina Red
Tennessee Green
No it isn’t. I think you are probably misinterpreting the problem. It’s fairly easy to visualize why a sphere is equivalent to the plane, as far as this problem goes:
Imagine your sphere sitting exactly the plane, with it’s “south pole” just touching it. If you take the “north pole” of the sphere, you can draw a line from that point to any point on the sphere, and continue the line out to the plane, projecting the point on the sphere to a distinct point on the plane (except for the pole itself). Conversely, if you take any point on the plane, and draw a line to the pole of the sphere, it will intersect the sphere in one place. So you can project any areas drawn on the sphere (sans north pole) onto areas on the plane and vice-versa. Distorted areas, yes, but it won’t disturb the border relationships. And you can orient the sphere so that the pole is in the middle of an area, so you don’t have to worry about that.
BTW, the way you work on this problem is not actually by coloring areas on maps, but the equivalent problem of coloring the nodes of networks (“graphs” is the more proper term) drawn on the surface with no lines crossing (“embedded in the surface” is the more proper term). If you like, imagine a capital city in each of the “countries”, and draw lines from it to each of the other cities in bordering countries through the common border without crossing any lines. If you can color the cities, you can color the countries.
As observed, it’s seven on a doughnut, a form of “sphere with 1 handle”. The thing that applies there is a thing called the “Heawood coloring theorem”, which gives you an upper bound number for any positive number handles (surfaces with any number of holes in them). It was Heawood that discovered the flaw in the early proof of the 4 color theorem after it had stood for several years. As an undergrad (a long time ago), I once presented the Heawood theorem as a seminar topic.
BTW, it takes six on a moebius strip.
The proper coloring would be Washington DC green, Tennessee blue, North Carolina red. What you’re missing here is that the map problem does not allow for a “region” to have non-continuous parts (like Michigan). When that’s the case, the map works as long as no two contiguous regions have the same color. You don’t need to have all six states bordering Virginia to be different colors; if it weren’t for DC, you could do the whole region using three colors.
What you are probably missing is that there are also requirements about common contiguity. Sure, you can have areas that border on a lot of other areas, but many of those other areas may be the same color because they, in turn, don’t border on each other. The restriction is not that all your neighbors have distinct colors, it’s that no two areas with a border are the same color.
Goody! A serious discussion of the four-color map theorem! (I had tried to start one of these a year or so ago, but it was quickly hijacked by people who did not understand the word “contiguous.”)
Another point worth making: on real maps, all water must always be blue; no land area can ever be blue (or at least not the same shade of blue). On these theoretical maps, there are no such restrictions. Any area can be any color, so long as no two adjacent areas are the same color.
Which leads me to my question. I have a simple explanation for the phenomenon. But I assume it is not a “proof.” (Pehaps this is the simple, hole-filled proof Mr. Kennedy alludes to.) So, assuming there is something wrong with this, I present it so the math whizzes can show me where I went wrong:
Start with a flat surface. Divide it into any number of areas. The rules of contiguity and no-special-color-for-water apply.
Pick any area. Count how many neighbors it has – how many other areas it shares a border with. (A border being a line segment, and not just a single point.)
The number of areas must be a whole, positive number. It will thus be either odd or even.
If the number of neighbors is even, then you need only three colors (red for the central area, and then alternate blue and green for the others).
Example: Iowa red, Minnesota blue, Wisconsin green, Illinois blue, Missouri green, Nebraska blue, South Dakota Green.
If the number of neighbors is odd, then you need four colors (red for the central area, alternate blue and green, and then insert one yellow so you don’t get two blues next to each other.)
Example: Nevada red, California blue, Arizona green, Utah blue, Idaho green, and then Oregon yellow, since it also borders blue California.
It is possible that you may have a small area (like DC in the earlier example) that is surrounded by areas you are coloring. This can add a complication – but if you find such an area, just use it as your starting point and assign colors from there.
Clearly, this is too simple. But I can’t see where it goes wrong. Can someone help? Thanks!
– Beruang
Beruang: I shall try to describe a counter-example to what I think you are suggesting, but it might not be easy without pictures.
Draw 2 concentric circles. Colour the inner one red ( say). Divide the outer circle into 4 sections and colour them alternately blue and green. Reading clockwise, label them B1, G1, B2 and G2. Now draw a region touching B1 and G1. This must be coloured either red or yellow and it doesn’t matter which. Choose yellow and label this region Y. Now draw a region which borders both B2 and G2 and curves round so as to touch Y as well. This region must be coloured red; call it R. But now there is a region which borders B1, G2 Y and R and so this colouring startegy fails.
There is in fact, one real world case that requires 5 colors. As far as I know, it’s the only one.
The five regions are Germany, France, Belgium, the Netherlands, and the ocean. All of these border each other in Europe except for France and the Netherlands. However, the island of St. Martin in the Caribbean is split between France and the Netherlands, giving them a border. Thus 5 regions all border each other so they require 5 colors.
Jonathan Chace,
this should clear things up a bit: http://www.math.gatech.edu/~thomas/FC/fourcolor.html
Grizz:
5 will definitely do it (proven); but 4 has been shown to do it in all possible scenarios (experimental conclusion). so if you trust the computer and the people programming it, 4 is all you need.
i got to hammer this out with crayons in a 300 level math class two years ago. geesh.
Oops I screwed the pooch on that one. Anyway here’s how I remember it and maybe it’ll help JC.
A man wanted to split up his farm into five different plots so that each one of his sons could have part. However, he wanted each plot to have at least one side touching each of the other four so that all five had at least one side in common with all the others. The catch though was that he did not want any land split in two parts.
I hope I got that right but the point is that there is no way to have five plots of land all touching all of the other ones. however it causes problems when you have countries that are split in two like the US then it is possible. I think, though I will have to look it up, that most maps use a minimum of five colors and usually six because of the cost of extra colors makes printing go up. If I remember I will try and look it up.
Jabba, Beruang’s coloring scheme obviously requires that a mixture of odd-neighbor and even-neighbor regions must be colored using the largest number of colors. In the case you give, there are three-neighbor regions as well as four-neighbor regions.