Talk:Four color theorem

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Mathematics.
	Mathematics grading:	A Class	High Importance	Field: Geometry and topology
Expand section on "Non-contiguous regions", then consider nominating for Featured Article status. Tompw 19:18, 7 October 2006 (UTC)

Archives:

• /archive1 - discussions from before July 2005.
• /archive2 - discussion about the validity of an alleged proof by Dharwadker.

Contents 1 (Most likely not a) counter-example 2 Not for map-makers 3 Comment on recent edits 4 Make it clear! 5 Four-coloring the real world 6 ¿NP-COMPLETE? 7 why the move? 8 Image to remove? 9 what about this 10 3D equivalent? 11 Describing the best known algorithm 12 Spencer-Brown 13 "Not for Mapmakers" vs. "Real-world counterexamples" 14 Confusing...

[edit] (Most likely not a) counter-example

Consider the map to the right; it obviously cannot be colored with only four colors without repeating one of them in two adjacent regions. This clearly goes against what the theorem states.

I'm not disputing the theorem; the flaw must obviously be in the way I'm interpreting the theorem's conditions (I don't know Graph Theory). But to say that every geographical map can be colored this way is thus misleading, since in my view this map is as "legitimate" as any other.

Would someone care to enlighten me? Also, apologies if you think I should have posted this to some discussion group about Mathematics instead -- but IMO the article should be reworded, and besides Wikipedia is such a great place to find answers ;)

--Doshell 13:31, Apr 6, 2005 (UTC)

If you color the yellow region grey, and the green region blue, then you get a map with three colors. I won't make a picture, but the following should suffice.

      +------+-----+
      | Blue |     |
      +------+     |
      | Grey |     |
      +------+ Red |
      | Blue |     |
      +------+     |
      | Grey |     |
      +------+-----+

Can you think of a reformulation of the statement which clarifies the issue? I'm afraid I don't see exactly where the problem is. -- Jitse Niesen 13:56, 6 Apr 2005 (UTC)

How stupid of me. You're totally right; in fact, the article doesn't need to be clarified at all. Goes to show that you should put a little more thought in everything :) --Doshell 19:12, Apr 6, 2005 (UTC)

Example right. I'd put this down to simple brainfade - I've made similar errors myself in the past :) sjorford →•← 14:00, 6 Apr 2005 (UTC)

The example is a poor one, and should be removed from the article. The article states that it seems to require 5 colors, presumably because the grey area cannot simply be colored red, yellow or blue without re-coloring. However, it *can* be colored green, and that doesn't require shuffling any of the other colors around. This makes it a very misleading counterexample. I know I spent a lot of time scratching my head wondering why this was considered a counter-example at all, and how the caption made any sense. Please either replace it with an example which does need to be re-colored in order to work or remove it (not that I don't think it's a valiant attempt, but it's just confusing). Thanks. -Harmil 21:31, 9 August 2005 (UTC)

Hey Harmil, how about this one. I believe it requires at least four colour changes (out of ten regions) in order to get a proper 4-colouring. Dmharvey Talk 11:10, 10 August 2005 (UTC)

I agree, Harmil - I never intended it to go in the article, just on the talk page. It's far too basic. Dmharvey - can you post a 4-colouring that only needs 4 changes - I can't work it out in so few! sjorford #£@%&$?! 15:11, 1 September 2005 (UTC)

Sure I'll try to do it later today. Dmharvey Talk 16:44, 1 September 2005 (UTC)

Here it is:

Sketch of proof that four colour changes are required: Suppose you try to get rid of the blue regions. Trouble is, each blue region touches all four other colours, the regions touching the inside blue one are disjoint from the regions touching the outside blue one. So in this case you need at least four changes. OK, so suppose instead you try to get rid of the red ones. (All other colours are symmetrical to the red ones, so handling red is good enough.) In this case there is a region touching both red regions (in fact you could pick either the yellow or the purple one), but it touches all three non-red colours. So here again, three changes aren't good enough. Have fun writing this more coherently ;-) Dmharvey Talk 17:40, 1 September 2005 (UTC)

I apologise for including that poor example. It was just what was handy. I like your example more. Deco 21:12, 1 September 2005 (UTC)

I had a similar thougth to the original poster - and I'm sure that I am just not understanding something correctly. Here is my diagram. I would love to know why this is not a proper counter-example:

+------------------------------------------+
|    Red                                   |
| +-------+  +------+ +--------+ +-------+ |
| | Blue  |  | Grey | | Yellow | | Green | |
| +-------+  +------+ +--------+ +-------+ |
+------------------------------------------+

I'm sure there is something in the difining of the problem that makes this counter example invalid but I don't see it. Thanks --Corey

Same again - you can colour all of the enclaves blue! sjorford →•← 16:55, 6 Apr 2005 (UTC)

  +------------------------------------------+
  |    Red                                   |
  | +-------+  +------+ +--------+ +-------+ |
  | | Blue  |  | Blue | |  Blue  | |  Blue | |
  | +-------+  +------+ +--------+ +-------+ |
  +------------------------------------------+

[edit] Not for map-makers

The four colour theorem does not arise out of and has no origin in practical cartography. According to Kenneth May, a mathematical historian who studied a sample of atlases in the Library of Congress, there is no tendency to minimise the number of colors used. Maps utilizing only four colors are rare, and those that do usually require only three.

Can someone check the last sentence in this paragraph? It is wrong (maps utilizing four colors use only three colors?) . I don't know anything about maps but I guess it should be: Maps utilizing only four colors are rare, and those that MINIMIZE THE NUMBER OF COLORS USED do usually require only three. But then it seems strange to me that cartographic maps that minimize colors usually need three colors.

I reread this, I misunderstood it. They're saying that most maps use more than four colours, and when four colours are used, usually three suffice. In other words, mapmakers tend to pretty much always use more colours than necessary. Not sure how to rephrase this. Deco 1 July 2005 00:19 (UTC)

I actually think it's pretty clear as it stands. Dmharvey Talk 1 July 2005 00:51 (UTC)

On another note, I'd think that the requirement on some practical maps that non-contiguous regions have the same color (for example: coloring Alaska , Hawaii and the continental US all the same color on a world map) would fuck up the theorem, however I'm not sure if this is true or not. Anyone know? It should be in the "Not for map makers" section if it is true. -- Tyler 09:22, 27 September 2005 (UTC)

• That's a good point. While the US is not a good example (I don't think that there are any on Earth anymore, but I might be wrong) the idea destroys the theorem for actual maps with non-contiguous regions of the same color. --Apyule 13:26, 27 September 2005 (UTC)

Isn't this already mentioned in the opening paragraph? Dmharvey Talk 23:01, 27 September 2005 (UTC)

And in the whole section at the bottom ("real-world counterexamples")! I have no idea how I missed all that... I suppose I expected to find it in the section "Not for map-makers" and assumed it wasn't there at all. D'oh! -- Tyler 23:41, 27 September 2005 (UTC)

• if there is only one discontinuous country then 7 colors neccesarily suffice: if you imagine an underground tunnel connecting the two areas and chonsider the walls of the tunnel, you get a torus surface. And as the article says, 7 colors suffice to color any torus.Honnza 08:39, 14 July 2006 (UTC)

[edit] Comment on recent edits

Some of the material added by Ewlyahoocom doesn't seem particularly encyclopaedic. Anyone agree? Dmharvey Talk 21:09, 29 September 2005 (UTC)

I agree. Ewlyahoocom 13:50, 30 September 2005 (UTC)

I've looked around a little bit. How-to suggests Wikibooks as a better place to put the How-To kind of information I'm envisioning. I'll investigate some more. Ewlyahoocom 08:21, 2 October 2005 (UTC)

[edit] Make it clear!

This theorum looks like:

No matter how you divide a 2D plane, you can't construct a series of divided areas that results in, when only four colours are applied, no two similarly coloured areas will touch.

Hence: the very simplistic counter-examples of a long rectangle abutting four smaller rectangles, or a cirlce interposed over four squares.

It should say:

No matter how you divide a 2D plane, you never need more than four colours to ensure that no two similarly coloured areas will touch.

Isn't that what the first sentence already says? Dmharvey Talk 20:47, 2 October 2005 (UTC)

I agree, the first sentence is very ambiguous and at first glance seems to say that no more than four colors can be used to satisfy the property.

I believe it has been proven that a counterexample cannot exist...am I wrong? Yet I see reference to that proof.

---

The problem be summarized to the following: On a plane where you have 5 points can you connect each point to the other without intersecting any lines.

---

What is actually meant by 'plane'? I see here that points are used to represent areas and lines connecting those points are used to represent contiguity. But that is exactly what I did when as a child I figured I had 'proven' the theorem or conjecture yet my math teacher claimed that since obviously a solution a child could come up with could not be correct there must be some problem with my proof, possibly, for all he knew, it might not have been proven at that time that points connected to lines are toplogically equivalent to areas connected by contiguity. Basically he agreed that it sure did look like if points are in fact equivalent to areas and lines connecting points are actually equivalent to contiguity then sure it was indeed blatantly obvious a proof. So maybe in those days (1968 or thereabouts) it had not yet been proven that points connected by lines can validly (formally, axiomatically, theorematically, or rigorously or some such adjective) represent or correspond to areas connected by contiguities?

As a child my solution had simply been to observe that three connected points is topologically equivalent to a circle and that thus any fourth point (representing a fourth area) must be inside that circle or outside that circle or on that circle. Regardless of wether it is inside or outside, if needs three lines to connect it to the pre-existing three. It is actually irrelevant whether you picked inside or outside to place the fourth point, in either case the result is (topologically equivalent to) a tripartite circle (or a plan view of a tetrahedron). Thus in either case you have surrounded one of the four colours, freeing it up to be used again. No matter where you put the fourth point (area) you surround one of the three or place the fourth where it itself is surrounded. So always it is free to used for the next point you choose to add.

So topologically, by deforming the plane like some kind of fractal affine-transformation kind of deal (topogical sretching and deforming), it seemed pretty much obviously proven. Meanwhile if you choose to define a plane as that which is defined by three points, being as how three points on a plane defines a plane, then maybe you are looking at whether a plane need have any more than three points, and if it does where do you put them, what shape are they, and how many, exactly, are there, because you might as well colour points instead of regions unless oh wait a sec, how many points can all mutually be congruent on a plane of X number of points? Are we talking about a quantum plane, maybe using Buckminster Fuller vector equilibria as edges or points? Or a classical plane? If a classical plane does that permit topology or only Euclidean geometry?

Yeah I know, I have been way too many hours without sleep. Sorry. But still, surely how you define a plane makes a lot of difference, and when exactly did it get proven that points and lines are actually useable in proofs of plane geometry? Or is it only a proof of topology not strictly of plane geometry?

Basically for umpteen years I have yet to find anything that makes clear what is unproven or unprovable about 'the simple proof'... such as the one the originator of the conundrum had in mind maybe hmm, if they didnt have a huge computer-proof in mind; wasn't part of the whole conundrum the fact that supposedly the proof was simple? (Um, no, maybe not; I am maybe thinking of Fermat's Last as the one someone claimed was simple and elegant but didnt write in margin.)

What seemed simple about the points and lines method was that you show ab initio that starting from the very first area each time you add an area you automatically free up a colour each time you add an area that requires a fourth colour, so provided you correct your previous colour-scheme each time you add an area you need never get confused enough during the course of building the map to ever lose track of the fact that you never needed a fifth colour. Thus you do not find yourself looking at some hugely complicated map wondering how to colour it, you instead see step by step during construction that you have enough colours to be able to add another area if you want to.

Knotwork 11:34, 23 August 2006 (UTC)

I think that not every planar graph can be obtained by the method you describe. What happens to your algorithm for the graph formed by the vertices and edges of an octahedron? What colouring does it produce? Dmharvey 20:13, 23 August 2006 (UTC)

In short, yes, you are thinking of Fermat's Last Theorem. Most people believe that Fermat's proof was probably incorrect, like those of many others to later work on the theorem. The Four Color Theorem also had a very large number of incorrect proofs, the most notable of which stood unchallenged for over a decade. Your solution is not correct, because it's not hard to show that for certain planar graphs, you can find a greedy coloring sequence which uses an arbitrarily large number of colors. In other words, unless you constrain the greedy coloring sequence in some way, which you do not appear to do, it will not succeed in four coloring an arbitrarily planar graph. Deco 23:14, 23 August 2006 (UTC)

Following the references for such things as the five colour theorem I notice there is a whole science of colouring edges and nodes of graphs. Is chromodynamics the use of such graphs for stochastic mechanics, or something like that? As in, is this stuff about colouring graphs actually a step toward quantum electrodynamics? Using colours such as up, down, top, bottom, strange and charmed and stuff like that?

Knotwork 16:07, 23 August 2006 (UTC)

[edit] Four-coloring the real world

I believe it is true that despite the existence of several countries that are in multiple sections, the political map of the real world happens to be 4-colorable. In most case the extra sections don't add any complexity: for example, Alaska only borders Canada, which already borders the Lower 48 States. Ceuta only borders Morocco, and the main part of Spain could be extended to touch Morocco without interfering with any other borders. And so on for most of the others; island territories don't matter at all.

Russia and Azerbaijan do add complexity, but I think it happens to be true that it can be worked around. I say "I think" because I worked it out to my satisfaction once, but I never showed it to anybody else.

Can anyone either confirm this from a reliable source, or else disconfirm it by listing a group of adjacent countries that require 5 colors (ignoring water areas)? I think this is a point worth mentioning in the article.

--Anonymous, 07:20 UTC, November 16, 2005

This is an interesting point, although I'm not sure how relevant. There's only one country contained within another as far as I know, and it doesn't pose a problem. If you include water, there are many contained bodies of water, so I'm betting you'd need 5 colours, but you're excluding those. I can't think of any counterexample, but I haven't seen a complete 4-color world map done. Deco 09:09, 16 November 2005 (UTC)

I think this would be a great bit of trivia to have in the article. I shall look into it. Equalpants 00:13, 12 January 2006 (UTC)

If you ignore the geographical features (Coloring the lakes with different colors throughout the map, Alaska blue and USA red, antarctica yellow, etc.), you are able to color the world with four colors. I'm not sure about the globe, but a 2-D map is possible. --24.149.204.116 13:48, 1 August 2006 (UTC)

[edit] ¿NP-COMPLETE?

The article says: "Determining whether 3 colors suffices is, however, NP-complete, and so unlikely to have a fast solution. Determining whether a general (possibly non-planar) graph can be 4-colored is also NP-complete."

Can someone pass me a link that proves that those problems are NP-complete? They can't be NP-complete, because I found an easy way to tell wether 3 or 4 colors are enough (or not) for coloring any general graph. I didn't know this was considered a NP-complete problem, so I didn't gave it much importance then. DrJones 20:18, 10 December 2005 (UTC)

No, no you didn't. Your solution is incorrect. These problems are NP-complete. See the references section of graph coloring problem, or the NP Guide (ISBN 0716710455). You may be thinking of a different version of the problems — if you'd show us your solution I might be able to help figure out what's going on. Deco 20:22, 10 December 2005 (UTC)

Cool. Now that I know that this problem is deemed NP-complete, I'll try harder refuting my own solution. There's also the chance that the method could be exponential in the worst case scenario. I didn't expect anybody would care about it, so I just researched until it was enough to convice myself. :-)

I have homework to do next week, but I'll try to draw some pictures with which this will be easier to explain. I also must find where I wrote back the algorythm. DrJones 13:39, 11 December 2005 (UTC)

I finally was able to take a look to that NP-guide. According to it, it is an open problem (the entry is called [open5], I think), not an NP-complete one, that's it, at time of publication (1979) there wasn't any proof of its NP-completeness.

I also was able to proof that my solution is right. I'm very happy. At the same time, I've proven that the Four color theorem is wrong, because everybody (even me) missed something.

What's really wonderful. Now that I have the solution in my hands, I have been able to see something truly amazing!! I tried my algorythm for solving certain problem, and discovered that, when working in a direction, the complexity must be exponential, but working from the other way, it's polinomial, and I know what causes this behaviour.

Sadly, because the string of problems defined in N has a start, but not and end, you can't know beforehand what's the best point for starting backwards. So, if you have bad luck, you will be forced to continuously work on the exponential direction. THIS FINDING IS SO AWESOME, THAT NOW I DON'T MIND IF SOMEONE PROVES THAT MY SOLUTION DOESN'T WORK. YAI!!! DrJones 10:29, 13 December 2005 (UTC)

I'm afraid you're mistaken. It's listed as A1.1: GT4, pg.191, the Chromatic Number problem, which discusses both the general case and the planar special case. Graph coloring was one of the first problems shown NP-complete, and the reduction from 3-SAT was shown by Richard Karp in his seminal "Reducibility Among Combinatorial Problems." If you're not convinced by that, here are some additional web sources. [1][2] There are related open problems, some of which are discussed at [3]. It's good that you want to explore the problem, but honestly the chances that your current solution is correct are very slim; all the techniques you know have been available to the cleverest researchers in the area for many decades, and it's likely that they relativize, which would contradict known oracle results. Additionally, the four colour theorem is a proven theorem; it is not wrong. Your explanation of working in directions and exponential time didn't make any sense to me. And well, you probably should care if your solution is wrong. I hope this helps. Deco 18:49, 13 December 2005 (UTC)

Don't get me wrong. With I don't mind if someone proves that my solution doesn't work I meant that I was so happy, that being proven wrong wouldn't spoil me the day. See, I enjoy both looking for a method to solve the problem, and looking for a counter-example that disproves me. For every single attempt I have made so far, I've been able to find the flaw in it. This time, I've been unable to spot the flaw, and I think I have been able to prove the "if and only if" clause for the first time. That's why I'm so happy.

Second. I know the four colour theorem is a proven theorem, in fact, I think I've proven it using another, simpler approach. So, then why I said before that the theorem is wrong? Because the method I developed found the first real counter-example to it. Don't worry, the theorem still works, that's the fun part of it!

Sorry for not being more precise. I really want to talk to someone about this; I want to explain my method, let people review and discuss it, and help me spotting where is the flaw, if there's one. It's just that I want to avoid any chance of trouble with researchers claiming that I have stolen their ideas (moreover, I usually start by avoiding all previous works, to avoid taking the same dead-ends; I study them when I'm no longer able to advance). I'm clueless because I've never done this step before. Is it safe posting it on this page? Should I post it on Usenet? Writing a commercial program and sell it for money? (just kidding) Please help! :-( DrJones 23:08, 13 December 2005 (UTC)

I understand your reluctance, but I wouldn't seriously consider theft to be a problem. Most researchers treat the ethics of plagiarism with great respect, and most non-researchers don't have access to publications. You're more likely to profit from useful discussion about your algorithm than from withholding it. If you want to be extra paranoid, you can sign your description using PGP or something, and also submit it to the PGP Digital Timestamping Service, who would be able to later testify that you did write the document and you did write it at this time. Deco 23:21, 13 December 2005 (UTC)

Please, tell me that the problem of finding the chromatic number is not NP-Hard, please. This is getting scary. My algorithm might be used to break modern cryptography! (Edit: As long as there is a Np-complete version of the factoring problem) DrJones 10:53, 17 December 2005 (UTC)

The chromatic number problem is NP-hard. Your algorithm is almost certainly incorrect, as many people smarter than you and me have tried to find fast algorithms for this specific problem - I wouldn't know without seeing it. Integer factorization is probably not NP-hard, as this would imply NP=coNP, a result widely believed to be false (see integer factorization). Most people believe its decision version is either in P or neither in P nor NP-complete. A polytime algorithm for chromatic number would imply a polytime factoring algorithm, however. If your algorithm is really correct, come back and visit after you've claimed your $625,000 from the RSA Factoring Challenge. Deco 00:32, 12 January 2006 (UTC)

I recently found that my algorithm would only calculate in polynomial time the chromatic number only for graphs with certain property, which large graphs usually don't have. One thing less to worry. DrJones 14:01, 1 February 2006 (UTC)

So, then why I said before that the theorem is wrong? Because the method I developed found the first real counter-example to it. Don't worry, the theorem still works, that's the fun part of it!

You either have a valid counter-example or you don't. There's nothing in between. Judging from my experiences with other users you probably don't. Aragorn2 19:20, 19 June 2006 (UTC)

Yes. There is it. If you allow regions to be their own neighbors (say, a snail shape, for example), you have a planar graph with loops, which cannot be colored at all. The 4 color theorem is still valid because it states clearly that it only applies to graphs without loops. When you translate the map to a graph, you'll usually disallow a region to be its own neighbor, so the counterexample never happens. DrJones 18:55, 9 August 2006 (UTC)

That's covered in the generalizations section. You're describing a taurus (or something like it, I'm not too up on my non-euclidian geometry), and the page says that it's colored with a maximum of 7 colors. They even give a nice little formula for determining what the maximum colors will be. --68.82.180.187 00:08, 25 August 2006 (UTC)

Duh. I will try to make it clear my point.

a) A node cannot have the same color than its neighbors.

b) A node can be its own neighbor if it has an edge connected to itself (this is called a loop).

c) When you map the regions to a graph, you most likely don't translate self-touching regions as loops.

d) But if you did, you would find maps that cannot be colored at all. And this doesn't go against the four color theorem, because it states that it doesn't work with graphs with loops.

In conclussion, it's not that there aren't "real world counterexamples", is that we naturally transform them into colorable maps during the translation to the subjacent graph. DrJones 09:14, 29 August 2006 (UTC)

[edit] why the move?

Surely there is a policy against moving articles to change between UK/US spelling? I mean, it just seems like a waste of everyone's time.... it was perfectly fine at Four color theorem, no need to move it, and I'm speaking as someone who uses british spelling habitually. Dmharvey 22:49, 24 January 2006 (UTC)

Agreed. This contradicts policy (which is to use one spelling convention consistently in each article and not change it for no good reason) and is disruptive. Putting it back. Deco 01:35, 25 January 2006 (UTC)

FYI, anonymous user User:143.210.44.211 is the culprit. I suspect they're a simple vandal up to no good. Deco 01:36, 25 January 2006 (UTC)

I have reverted all changes by User:143.210.44.211, as well as subsequent partial fixes of those changes, and moved the page back to its original location. Deco 01:38, 25 January 2006 (UTC)

Good stuff. (For others' reference, it was reverted to the 15th Jan version: [4]). Dmharvey 03:00, 25 January 2006 (UTC)

[edit] Image to remove?

It seems to me that the Image:FourColorMapEx.png is not very informative. We have some nice examples in the article so I would suggestto remove it. What do you think? kuszi 09:45, 31 March 2006 (UTC).

I like that image and think it should stay. It's a good introductory example of the type of objects the 4-color theorem is concerned with. Among other things, it emphasizes the fact that the theorem is not really concerned with real-life maps. Redquark 17:44, 10 April 2006 (UTC)

I am convinced kuszi 21:24, 4 June 2006 (UTC).

[edit] what about this

I'm pretty sure you can't color this with 4 colors.

Colour the outside band red, and then the five interior strips in blue, green, blue, green, blue, in that order. So actually three colours is enough. Dmharvey 01:55, 22 April 2006 (UTC)

You got me there. Brun8 17:12, 22 April 2006 (UTC)

You can color that with only 3 colors.

because the person drawing the map is focused on the one large region, they fail to notice that the remaining regions can in fact be colored with two colors.

[edit] 3D equivalent?

How many colors are needed to paint the surfaces of adjacent solids inside a 3D container? Think in coloring humans internal organs as whimsical as possible in order no two touching organs having the same color?

No finite number is enough. For example, suppose you have n organs, represented by small balls floating in space somewhere. For each organ, grow n−1 "tentacles" out from that organ to touch each other one. You can do this without any of the tentacles intersecting each other. Now "inflate" each tentacle until you've filled up all the available space. So now you have n organs all touching each other. So you need at least n colours. Dmharvey 16:11, 26 May 2006 (UTC)

Another question: How many colors are needed if two faces meeting at a corner may not be the same color but there may be up to n faces at a corner (e.g. how many colors are needed to color a planar graph containing hyperedges up to n nodes)? it's evident that for n=2 and n=3 the answer is the same while for n=4 (orthogonal maps) four colors are not enough. --Honnza 14:55, 29 May 2006 (UTC)

Nice question. You can get a rough (and finite) upper bound for any n as follows. Say for example n = 4. At each intersection point where four faces meet, you can "pull apart" to obtain a new map, like this:

AAAAABBBBB          AAABBBBBBB
AAAAABBBBB          AAABBBBBBB
AAAAABBBBB    =>    AAABBBBBBB
CCCCCDDDDD          CCCCCCCDDD
CCCCCDDDDD          CCCCCCCDDD
CCCCCDDDDD          CCCCCCCDDD

This produces a new map where only 3 faces meet at each vertex. Colour this with 4 colours using the usual 4ct. Now try to join them back together to see what goes wrong. In the above example, A and D might have the same colour, which is bad. But if you consider the set of faces that got assigned that colour, that itself forms a planar graph, so you can split that set into at most four subsets, and colour them each a different colour. So you need at most 16 = 4×4 colours in this case. I think you can do something similar for any n. But I doubt the bounds you get in this way are optimal. Dmharvey 16:15, 29 May 2006 (UTC)

great answer, Thank you. Even though the upper bound might not be optimal, as you say, it's a great proof that it is finite and gives us a hint that it is finite for any n (I might prove it later, the current status is something between a theorem and guess :-))

Hello once again. For any n, just pull out one face from a vertex of this order. Then color it using the n-1 coloring. Induction presumption is that it is possible to color it using at most c colors. Then push the map back together. Connecting graph nodes (map faces) gives us at most c planar graphs (since at one vertex there can be only one collision), not neccesarily connected. You can four-color all of them. So you need 4c colors at most. So c(n)=4^(n-2) is enough for any n>2.

[edit] Describing the best known algorithm

I'm thinking of adding a more detailed discussion of the specific algorithm described in "Efficiently four-coloring planar graphs" by Robertson, Sanders, Seymour, and Thomas, with enough detail to enable an implementation. Would appreciate any positive or negative feedback on this idea. Deco 19:54, 8 August 2006 (UTC)

Update: I've described the linear-time five-coloring algorithm from the same paper at five color theorem. Deco 00:32, 9 August 2006 (UTC)

[edit] Spencer-Brown

I added a short hint of George Spencer-Brown's proof in the part "history". Maybe it is grammatically wrong, because I am German. Please correct it. Bullpit 31/08/2006

[edit] "Not for Mapmakers" vs. "Real-world counterexamples"

The information in these two sections is really starting to overlap. For example, the issue of coloring water bodies is repeated with slightly different rationale in each. What should be done to merge them? --Jonrock 23:00, 30 September 2006 (UTC)

[edit] Confusing...

Is this article saying that with any map. you can colour it with at most 4 colours, so that the same colour doesn't touch itself? If so, is the picture of the tessellated parallelograms — which apparently needs 7 colours to colour it in — a counter-proof? I'm not exactly a mathematician, so if someone could correct me (or possibly the article?) that would be very nice. Thanks. Ian F. 21:22, 23 October 2006 (UTC)

That image is showing how the result changes when you go from a map on a plane to a map on a torus. The "shape" of the space you are drawing the map on is of fundamental importance to the result, as this section on "Generalizations" demonstrates. --Jonrock 01:00, 24 October 2006 (UTC)