There have been several more compact and “Math-like” proofs of the 4CP since H&A’s proof. I once attended a 30 minute talk on one of them and it only made my head ache a little.
Since all planar graphs (aka the kind of maps we’re talking about) take at most 4 colors the question becomes: which ones require 4 colors? Note that determining if a graph (planar or not) is 2-colorable is quite easy. So for a planar graph the hard question is: can it be done in 3 colors? This problem is NP-Complete. And if you can find an efficient test if a planar map is 3-colorable, you are Instantly World Famous. (Or conversely prove there is no efficient test.) This is one of the major open in problems in Computer Science. It has literally thousands of implications to Real World problems.
So, you might start off with a silly little Math problem but end up with something quite practical. Factoring numbers was once just a theoretic problem, now it’s at the core of some popular crypto systems. Simple questions that turn out to have hard answers teach us deep things about the universe.
Well if we start with an odd-coloured region we run into a problem even sooner.
Draw 2 concentric circles and colour the inner one red. Divide the outer circle into 5 sections. Reading clockwise, label them B1, G1, B2, G2, Y. Draw a region touching Y, G2 and B2. This must be coloured red; call it R. Finally draw another region bordering R, Y, B1 and G1; this region cannot be coloured.
Of course, I am not claiming that the 4-Colour Theorem is false, since it has been proved. I am saying that Beruang’s scheme is insufficient.
Anyone who has ever studied algorithms knows that almost anything interesting is NP-complete. For those wondering how we get anything done, understand that often only worst case behavior is exponential, and that time is linear or polynomical for most practical cases.
I was at Illinois when H&A announced their results, and went to their seminar. It was impressive.
As for computer power, the “proof” was done on a Cyber 7600 (I think) machine from CDC, which was mostly used to run the Plato system. (Anyone else here a former Plato user? It had most of the features of the Internet and Web in the mid-70s - except spam.)
Appel’s son Andrew, who was in high school at the time, did the programming and somehow got late night cycles to run them. He is now a professor at Princeton, and testified (for the good side) in the Microsoft case.
I, too, am unsatisfied with the “proof” Cecil mentioned in the 1984 column. I do intuitively understand it to be true, though.
Expanding on Arnold Winkelried’s earlier clarification
There is only one rule that must be followed (for planar surfaces):
You cannot be forced to “tie” two separate regions to the same color and expect the theorem to hold true. This is the only reason why so-called “real world” situations might refute the 4-color rule. In dtilque’s example, the island of St. Martin has two regions that are “tied” in color to their parent countries, France and the Netherlands. This is why 5 colors are needed in that situation.
Also note that, as Beruang pointed out, real-world maps must always use blue for water, thereby again violating the rule of tying separate regions to the same color.
There is also a method of coloring that must also be followed:
You must not color the cells before all the regions are designated.Jabba’s mistake was in specifying the colorings of the second ring of concentric circles before the remaining regions had been drawn. You can easily color in the regions in his(?) example using only 4 colors, but only after the whole figure is drawn without color first.
I am aware of the situation regarding the colouring of the 2 maps I described. As I said above I was not trying to refute the 4-Colour Theorem, which has been proved, but to show that Beruang’s proposed algorithm for determining a correct colouring was faulty. My examples were constructed specifically for that purpose.
It’s well known that if any region has an odd number > 1 of neighbors then the graph requires 4 colors. Do I take it correctly that there are graphs that do not have such a region but still require 4 colors?
Well, the first part is trivially false. Surround country A completely by country B. Add an even number of “Andorra” like countries along the border (none of which touch each other). A can be red, B can be blue and all the “Andorras” can be green. Lots of other counterexamples.
I think you misstated that. Take a K4, remove one of the edges. The result is three colorable, but two of the vertices have degree 3.
I see ftg just said something about this, so I won’t describe what I meant further, and I’ll add a cautionary note. If you are going to talk about graphs, you talk about coloring the nodes. Part of the purpose of converting the problem to graph theory is that it retains the essence of the question without having to worry about the actual shapes of the regions, which are essentially irrelevent to the discussion - we are only worried about their border relations, and the embedded graph retains that.
OK, I guess I hadn’t thought of all possible subgraphs that would match my description. What I was trying to get at was the case where one region is completely surrounded by an odd number of other regions. (It’s been years since I took graph theory, so I’ve forgotten a fair amount of the terminology. Sorry if I use the wrong word.)
So first eliminate all singleton nodes from the graph. That is, those that connect only to one other node. Then if one node has an odd number of neighbors, each of which is connected to at least two of the other neighbors, then we have a graph that requires four colors. This should be congruent to the case I described above.
My question is whether there are graphs that require four colors that do not have such a subgraph?
[QUOTE]
*Originally posted by emoryj *
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.
Thanks! You are correct – my algorithm does not work in the situations you describe. However, if you take those same maps and start with some OTHER area as your “first red,” the algorithm will work. In your first map, it will work if you start with either G1 or B2. But it will not work if you start with the last R. With the second map, it seems to work just fine if you start with any area OTHER than R1.
So, what I need is an algorithm to determine where to start applying the algorithm and… OK, I’ll stop now…
dtilque. I really don’t want to get into an infinite cycle of coming up with counterexamples to your conjectures, have you modify your conjectures, etc. It’s really, really, easy to come up with counterexamples. But it’s hard to explain them clearly in text. So I’m leaving it at that.
Yes but how much time does the H&A proof take on “any decent home pc”?
What’s the coloring-number when each territory is in n pieces?
Without resorting to stereographic projection as yabob did: Consider a map on a hollow rubber ball. Poke a hole within one of the territories; this obviously does not affect the coloring. Stretch out that hole until the ball becomes a flat sheet.
dtilque’s St Martin example may be unique for sovereign territories in the present day, but I’ll bet there are more examples on other levels or in other times; for example several Swiss cantons are in multiple pieces, as were some of the quasi-sovereign states in early modern Germany.
Voyager: I not only used Plato, I went to hi-skool with Appel’s and Haken’s children. Ken Appel came to our math class one day in 1974-5 to chat about the map problem. I did not know what computer was used for the proof, thanks!
The computer proof was more than experimental. Unless a mistake was made (and a lot of people examined it), it’s a really-o, truly-o mathematically valid proof. It’s just that mathematicians don’t like the idea of a proof that has tens of thousands of steps.
This brings up an interesting point: most theorems, and most proofs, are too long for us to understand. Of course, these are probably the most interesting ones.
It’s fairly easy to show that in three dimensions, no amount of colors suffices for an arbitrary map. Consider, for instance, a bunch of vinelike shapes (specifically, n of them). Each vine consists of a very long vertical stalk, with branches reaching out from it. Each vine has n-1 of these branches, and each branch reaches out to a different other stalk. I can do this for any n.
Martin Gardner once addressed the question of two-region countries, but with the stipulation that each two-region country consisted of one part on Earth and one part on the Moon. If I recall correctly, this required as many as seven colors. Certainly, the general solution for n-piece countries is at least 3+n (a fairly weak lower bound). Consider a large map which requires 4 colors, such that there are n particular countries which must be all the same color (say, red). Now, for each of those countries, give it n-1 embassies, each completely contained within one of the other red countries. Now all red countries “border” each other, so each must have a different color.
Is there a finite color-number in 3space if the `countries’ are convex? I can’t see a pathological case offhand, but that obviously doesn’t mean there isn’t one.
Unless it has some special meaning in topology that I don’t know, “convex” is taking the question out of the realm of topology and into ordinary geometry.