Talk:Four color theorem/Archive 3

Archive 1

Archive 2

Archive 3

Archive 4

Archive 5

(Most likely not a) counter-example

File:Five color map.png

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 File:User dmharvey sig.png Talk 11:10, 10 August 2005 (UTC)

Editors: The above example can be changed to a four-colored map with only 3 changes: 1) Change the bottom red to cyan (the center region color). 2) Change the top green to cyan (the center region color). 3) Change the top red to green. No fourth change is needed. It might be a good idea to correct the statement that "it is necessary to change at least four of the ten regions to obtain a coloring with only four colors." 75.61.106.153 04:28, 28 June 2007 (UTC)L Zuo

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 File:User dmharvey sig.png 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 File:User dmharvey sig.png 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 | |
  | +-------+  +------+ +--------+ +-------+ |
  +------------------------------------------+

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 File:User dmharvey sig.png 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 File:User dmharvey sig.png 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)

Comment on recent edits

Some of the material added by Ewlyahoocom doesn't seem particularly encyclopaedic. Anyone agree? Dmharvey File:User dmharvey sig.png 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)

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 File:User dmharvey sig.png 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)

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)

According to stereographic projection, it is possible. Yuide 10:38, 2 January 2007 (UTC)

¿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)

This is wrong. . .if you are speaking in terms of graph theory, then the theorem only applies to simple, undirected, planar graphs. Assume that your conversion from graphs to maps is correct. That means the four-color theorem is wrong. This is a contradiction because we know it's true, therefore your conversion cannot be correct.Citrus538 04:51, 12 October 2007 (UTC)

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)

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).

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.

I'm sure this one doesn't work either, I just had to have a try. Any thoughts?

--Nosfartu 21:57, 15 September 2007 (UTC)

Change the small purple region to green. Then change the small red region to blue. Then change the large purple region to red. This eliminates purple and colors the map with four colors. Eric119 22:18, 15 September 2007 (UTC)

Of course, it works.. I wish that I could think that quickly. The trick seems to be to look for the pieces with the least neighbors, so the trick is to try to maximize the number of neighbors I think. It just makes my head hurt though. Good job! --Nosfartu 22:29, 15 September 2007 (UTC)

It's really not very difficult to find a solution for these superman figure, if you first ignore the regions having less than four neighbors. If you find a solution irgnoring this small regions, one color of the four is allways left to color finally the small regions too. —Preceding unsigned comment added by 84.59.238.149 (talk) 16:48, 25 November 2007 (UTC)

I had to have one more try..

I really don't see a way to do this without a fifth color, but I do suppose I'm blind. I'll stop my challenges after this. Maybe someone will have fun solving this if it isn't easy or disregarding one of the rules. --Nosfartu 02:17, 16 September 2007 (UTC)

Change the red regions bordering the purple region to green, and then change the purple region to red. Eric119 18:51, 16 September 2007 (UTC)

And, now create four copies of the superman figure and place it to the top, bottom, left and right of the modified chess board. --88.68.103.51 (talk) 11:47, 25 November 2007 (UTC)

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.

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)

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

"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)

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)

I want people to see my own proof!

I know many people already tried to give a proof to the theorem in a simple manner and all of that, and they have failed. Well, I´m another person who wishes to try to solve this problem, even though it´s not likely I´m gonna do any better than all of those great mathematicians who have already done it. Anyway, where can I expose my own proof, so people can say what´s wrong about it? I see Wikipedia is probably not the best place, but I can see above on the talk page many people saying they´ve colored graphics in a way they need five colors (and failed), and no one complained... Is there a website or something in which this would be more appropriate?FoCoTh 00:09, 24 December 2006 (UTC) 21:22, 23 December 2006 (UTC)

The following text may be a little confusing because I didn´t spend much time making it easier to read, yet any kid that reads it two or three times and pays attention can understand it.

1- A map is made of sectors. Each sector shares its borders with other sectors. A map is nothing more than many sectors together.

2- The formation of any map (the drawing of any map) can be considered the expansion (the increase) of the number of sectors. And, as the number of sectors increase, so does the area of the map, because the area of the map is the area of all the sectors together.

-->What I mean is that any map which already exists can be drawn in a blank sheet of paper by doing this: draw ONE of the sectors, then another one, then another one, so the number of sectors is increasing and so is the area increasing and so on until the entire map is on the sheet of paper. It´s simple. There are other ways to draw the map, I´m just saying ANY MAP CAN BE DRAWN LIKE THAT. Get a sheet of paper and see for yourself.

(IMPORTANT NOTE: You can draw the map in many ways, actually. You can draw the TOTAL BORDER of the map first (like, in a square map, draw the square first) and then just "cut" the map into slices. If you imagine the map being drawn like that, it´s harder to understand the proof of the theorem.)

3- This expansion of the number of sectors is made necessarily by choosing 2 points of the first sector and then uniting them using a line different from that which already unites them.

---> Item 3 is very important to understand, and also very easy. Just get a sheet of paper, and draw a sector of your map. This can be a square, a circle, any closed area. Then, if you are going to build a map, the next sector must be touching the first one, I mean, they have to share a border. So, to draw the next sector, you will choose two points of your circle or square or anything and will draw a line between them. Try to do it and you will see it is true. Call it the "two points rule".

The "no points rule" comes next, and is the second and last rule.

IMPORTANT NOTE: you can draw the line "inside" your sector, dividing it in two sectors and not increasing the area of the map at all. Don´t do that. If your map will have two squares, one next to the other, don´t draw a rectangle and then divide it in two parts. Instead, draw one of the squares, then choose two points of the square and draw the other square next to it, from those two points. It will be the same at the end, but it´s much easier to follow the proof if you do it like that. (Remember ALL maps and ANY map at all can be drawn the way I´m saying.)

Practice a little.

Ammendment to item 3: There is another way of drawing the sectors. Draw a circle and then another bigger circle around it. You have a map with two sectors, and they are not drawn by the 2 points rule. That means the small circle shares it´s entire border with the big circle, and no other sector will touch the small circle, because it´s border is all shared with the big circle. The bigger circle was drawn without choosing two points from the small circle and uniting them with a line. It is the "no points rule".

There are just three rules to draw your map (any map can be drawn with those three rules) after the first sector is drawn:

-Two points rule: draw new sectors as you wish by choosing two points of the TOTAL BORDER of the map and making a line between them, not cutting the map, but in the outside of it. (in case there is only one sector, the total border of the map is the border of that sector)

-No points rule: draw sectors which "swallow" other sectors entirely as you wish. Draw sectors "swallowed" inside other sectors as you wish.

This third and more complicated rule you can learn later and it will be easier to understand once you finish reading this. You can skip it. It´s actually better that you skip it now.

-Swallowed maps: you can put another map inside your map, as long as the two maps have been constructed with the above rules. The new map, to be swallowed inside the first, can not touch more than one sector of the first, it must be swallowed by it, touching only one sector of it. (Notest that, if you want to build a map in which two maps are one next to another touching many sectors of one another, it can be done only with the two rules above.)

If you think you can build a map that cannot be built with only those three rules, think twice.

You must have understood the previous in order to understand the following.

Ignore completely the third rule for now, you will see why in a few minutes. Draw a sector. Draw a bigger sector all around it with the "no points rule". It can be a big circle or anything, and the first sector is inside it. Now, color the first small sector with color "1" (really, just write "1" in the sector, it´s easier). And in the bigger sector write color "2". If you continue drawing your map, you will see that there is never going to be another sector that touches sector 1 unless a swallowed smaller sector is put inside of it. That´s because sector 1 is inside sector 2, and so it will always be inside, because the two rules don´t allow anything else to be done, they only allow you to increase the area of the map, they don´t allow you to draw a little sector 3 touching sector one, because you always have to go adding sectors to the outside, never cutting the already existent sectors.

If you really want to have a little sector 3 touching the sector 1, then draw sector 1 first, sector 3 next using the "two points rule" and at the end draw the big circle around those two sectors, swallowing them both (using the "no points rule")

Let´s color all the maps from now on. Each sector will have one color. And I say no sector shall be colored the same color as a sector next to it! So, if one sector is red, all sectors touching it will have another color, like yellow or green. You don´t have to actually color them, just write 1, 2, 3 and 4 in each and everyone of them. Each number means they are colored in a specific color. The whole idea of this text is to prove you will never need a five.

OK. Now you have learned how to draw the map. Draw the map as I say: draw a sector. Draw another sector next to it. You do that by choosing two points of the first sector and then drawing a line between those two points, on the outside of the sector. You have a map of two sectors. Color one with color 1 and the other one with color 2. You can just write "1" and "2". Write "1" and "2", it´s much better. You will be coloring all the sectors of all maps from now on, but two sectors next to one another cannot have the same color.

You already have a map of two sectors, colored "1" and "2". Use the "no points rule" to draw a circle that swallows your entire map of two sectors. You will have a bigger map, with a circular TOTAL BORDER, with 3 sectors: one big sector that touches two smaller sectors that touch each other and also touch the biggest sector: or two little sectors inside a circular sector. Now, let´s say you don´t want your map to grow anymore. It will be just the size it is, so it will be a circle forever. You only need 3 colors to color that map, and I believe it´s really obvious to anyone, so I wont even explain it! You need only three colors, and it is proved. Color one to the first sector, color two to the second sector and color 3 for the bigger third sector.

However, "no points rule" allows us to draw small sectors as we wish inside those sectors already existent. You will have to color those new small sectors. Start drawing them, and you will see you still don´t need to use the "4". If you draw, say, a little sector inside sector one, it will only touch sector one, so it´s color can be "2" or even "3". It can also be "4" or "5", but the fact is you don´t need 4 nor 5 nor 3. Just use the smallest number possible, 2. Now, you can draw little swallowed sectors as you wish and you will never ever need to use the color "4", because swallowed sectors drawned like that will always touch only one sector, and thus they can all be colored 1 or 2. Notest you don´t even need the color "3" to color those new sectors. You would only need color three if those small new swallowed sectors touched two sectors, one colored "1" and the other "2". But they only touch one sector, always.

So, when do you need the fourth color?

Draw three sectors using only the "two points rule", in a way they all touch each other. So you will have to use colors 1, 2 and 3. We can call the sectors themselves sector 1, 2 and 3. Now, you can draw a fourth sector that touches all of those three sectors, and will thus be colored "4". There are two and only two ways of doing that:

-using the "two points rule" -using the "no points rule"

In the second case, the fourth sector will swallow the three sectors and then will be touching all of them and will have to be colored "4".

In the first case, you must choose two points of your map of three sectors. Look how interesting things go:

-If you choose two points of the border being that the two points are in, say, sector 1, then the sector 4 will only touch sector 1.

-If you choose two points of the border being that the two points are in, say, sector 2, then the sector 4 will only touch sector 2.

-If you choose two points of the border being that the two points are in, say, sector 3, then the sector 4 will only touch sector 3.

-If you choose two points, one in sector 1 and the other one in sector 2, you have two ways to draw sector four: in the first way, the line between the points will go directly from sector 1 to sector 2, a small line. If you draw this line, sector four will only touch sectors 1 and 2, and will be able to be colored 3. If you draw the line going from the point on the sector one to the point on the sector two by the "other side", in a way the line "closes" sector 3, then sector 4 will touch sectors 1, 2 and 3, and will have to be colored four.

HOWEVER, if you use the "no points rule" to swallow those 4 sectors with a new line, the new sector will be colored 3, because it will not be touching sector 3 at all, being that the line that forms sector 4 has closed sector 3 inside sectors 4, 3 and 2.

No other sector that you draw using "two points rule" and "no points rule" will ever be able to touch sector 3 more than once (the case in which you draw a swallowed sector inside of it).

Let´s see the third rule now. It allows maps drawn using "no points rule" and "two points rule" to be completely swallowed by sectors in other maps. Indeed, just try to do it and you will see that, in maps that use "no points rule" and "two points rule" only, there are never four colors on the border! As in our map sector 3 was closed inside sectors 4, 2 and 1, in all maps made this was you will always have to let one sector closed in order to achieve a fourth color.

If the color of the closed sector is 3 and you want to put this map inside the sector of another map, and this sector which will swallow the map has the color 1, it will touch the sector 1. Just change the colors, let color 1 be in the closed sector and color the other 3 sectors with colors 2, 3 and 4.

As there are only two dimensions on the plane, you will always have to "close" a sector, by going around it, in order to have a fourth color, and if one of the sectors is closed, the border of the map will always have only 3 colors at most.

21 3 4 82 7 23 04 8 FoCoTh 00:08, 24 December 2006 (UTC)

Talk pages of articles are for discussion on how to improve the article. A talk page is considered research for the article, and the policy of "no original research" also applies to talk pages.  --Lambiam^Talk 16:02, 25 December 2006 (UTC)

Some discussion of this is taking place at the Mathematics reference desk.  --Lambiam^Talk 17:46, 25 December 2006 (UTC)

The assertion that the border will never have four colors can be disproved with a counterexample map containing only six five sectors. Can this false proof be moved to an archive page? --Jonrock 07:26, 9 May 2007 (UTC)

Discharging Method

I recently created a page describing the Discharging method, which is one of the central ideas in the proof of the Four Color Theorem. Is anyone willing to read it and give feedback (it's my first significant contribution to wikipedia, so I'm eager to have other people look at it). Thanks. Ptrillian 07:30, 2 January 2007 (UTC)

chromaticity <= clique-minor number ?

could someone please disprove me that every graph of chromaticity n has a K_n minor? It is true for n=1 to 3 (dichromatic graphs do have an edge, trichromatic graphs contain a cycle and graphs without K₄ minor are either outerplanar or subdivisions of those and there's a unique (up to isomorphism) way to tricolor outerplanar triangulations and can be generalised to their subdivisions). If this was right for every n it would imply the four color theorem. Does there exist a nonplanar graph without a K₅ minor that needs 5 colors? 213.220.248.216 20:24, 9 January 2007 (UTC)

Congratulations! You have just reconjectured Hadwiger's conjecture. As you note, it can be easily proven for n≤4. Clearly the n=5 case implies the FCT; in fact they are equivalent (or so claims the wikiarticle; I certainly can't see the proof myself). The n=6 case is also true. All other cases are open. Unfortunately, there doesn't seem to be any proof of the n=5,6 cases other than via the FCT, so this doesn't allow an easier proof. Algebraist 23:35, 18 February 2007 (UTC)

ps. Bollobás' Modern Graph Theory sets as an exercise that if G has chromaticity 5 then G is contractible to K₅ or every vertex v of G is such that G-v is contractible to K₅ with one edge missing. So presumably that result is fairly easy. Algebraist 23:38, 18 February 2007 (UTC)

A new proof of the four color theorem

In 2000, the Indian mathematician Ashay Dharwadker discovered a new proof of the four color theorem [5]. Since the proof is written in the traditional style and does not depend on computer calculations, I suggest that the main article should be rewritten. 122.163.105.79 14:36, 14 May 2007 (UTC)

I think the Spanish version of the article is much better [6]! 122.163.169.144 11:06, 23 May 2007 (UTC)

Who added the word "alleged"?? It was not the original title of this fascinating discussion when the administrators archived it! You are supporting Cullinane? Just take a look at his user page and see what kind of reputation he has on wikipedia!

Thanks for bringing that to our attention. I corrected the Spanish article. -- Jitse Niesen (talk) 13:09, 23 May 2007 (UTC)

I did, too. (See corrected article) -- Cullinane 13:53, 23 May 2007 (UTC) and Cullinane 14:01, 23 May 2007 (UTC)

Well, I corrected it back, did you ask for permission from the Spanish mathematicians who wrote a better article than your english one? You, Jitse, just have a big ego problem because everybody knows that you lost that stupid argument with rstewart. You are just making yourself look worse now!

OMG! Jitse Niesen is now vandalising the spanish article!! Who made this guy an administrator??

The user "Rstewart" (very likely a sock puppet of Dharwadker) on June 23, 2007, removed a disputed-article template from the Spanish article. For comments on June 23 by "Rstewart," see the Spanish article's discussion. --Cullinane 00:16, 25 June 2007 (UTC)

Four-color-related vandalism

Anonymous user 122.163.102.246 on May 31, 2007, vandalized 25 math articles in Wikipedia. Note that the first six digits of the user's IP address agree with the New Delhi, India, IP address of some recent comments here in "A new proof of the four color theorem." For further details, see User talk:Cullinane.

-- Cullinane 01:25, 1 June 2007 (UTC)

Description of the Proof

Is there any possibility of including some intuitive description of the proof? I appreciate the original proof relied in part on computer work, but there must have been *some* intuition necessary to get to that point, right?

There is no reliable proof, since the theorem is simply wrong. --Fsswsb 19:27, 24 October 2007 (UTC)

Note that this has been discussed on User talk:Fsswsb#Four color theorem. (Fsswsb has been changing the article to show a 5-color image as "proof" that the theorem is wrong, even after I've posted the 4-color solution for it to his own user talk page and he replied to it.) You can see some examples and explanation there if you wish. --Closeapple 19:42, 24 October 2007 (UTC)

'color' or 'colour'

Is it normal within Wikipedia to use US english spellings? I know Wikipedia is very US-centric, so from that point of view the answer is yes. However, standard english would require standard english spelling i.e. 'colour'. Any consensus, bearing in mind the world doesn't begin and end at the US border? —Preceding unsigned comment added by Fizzackerly (talk • contribs) 12:07, 20 September 2007 (UTC)

The consensus is to use whatever the first major contributor used; see Wikipedia:Manual of Style#National varieties of English. -- Jitse Niesen (talk) 12:18, 20 September 2007 (UTC)

Purported disproofs

Purported disproof

Colored with four colors

File:ColorXXXfixed.png

Another purported disproof by User:Fsswsb : Can't be colored with four colors. The black region in the middle might be colored blue after exchanging the small blue and purple to the left and the right of black box. The white box on the upper right side might be colored red, and after flipping the blue and purple, the black one blue, but then, no more color is remaining for the big white in the lower right corner. Ok, one might color the black box on the right green after changing the small green boxes to red. Therefore, I added the big black box.

...correctly colored.

The two top diagrams are the purported disproofs added by User:Fsswsb, the two bottom diagrams are correctly colored by me. -- ArglebargleIV 22:38, 1 November 2007 (UTC)

Fair use rationale for Image:ColorXXX.png

Image:ColorXXX.png is being used on this article. I notice the image page specifies that the image is being used under fair use but there is no explanation or rationale as to why its use in this Wikipedia article constitutes fair use. In addition to the boilerplate fair use template, you must also write out on the image description page a specific explanation or rationale for why using this image in each article is consistent with fair use.

Please go to the image description page and edit it to include a fair use rationale. Using one of the templates at Wikipedia:Fair use rationale guideline is an easy way to insure that your image is in compliance with Wikipedia policy, but remember that you must complete the template. Do not simply insert a blank template on an image page.

If there is other fair use media, consider checking that you have specified the fair use rationale on the other images used on this page. Note that any fair use images uploaded after 4 May, 2006, and lacking such an explanation will be deleted one week after they have been uploaded, as described on criteria for speedy deletion. If you have any questions please ask them at the Media copyright questions page. Thank you.

BetacommandBot 15:48, 5 November 2007 (UTC)