Talk:Four color theorem

Archives:

• Archive 1 - discussions from before July 2005.
• Archive 2 - discussion about the validity of Ashay Dharwadker's proof of the four color theorem [1].
• Archive 3 - April 2005–September 2007

Possible Typographical Error

The article states that "...the regions may be colored using no more than four colors in such a way that no two adjacent regions receive the same color..." . I believe that it should state "no fewer than four colors".

Muranesenema (talk) 01:49, 21 October 2008 (UTC)

No, this is right. No more than four colors are needed, but some maps can be colored with less than four colors.—Tetracube (talk) 02:14, 21 October 2008 (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)

Real life examples of non-contiguous regions

The real life examples don't seem to hold. I can color the map of Azerbaijan (with its neighbors), or that of United States, or Russia without using more than 4 colors.Bless sins (talk) 23:28, 10 February 2008 (UTC)

The examples given are examples of enclaves -- regions separated into two or more noncontiguous parts. They aren't necessarily examples of non-four-colorable maps, but a map with non-contiguous regions is not guaranteed to be colorable with four colors. -- ArglebargleIV (talk) 00:10, 11 February 2008 (UTC)

Good ones! I was thinking of a simpler thing, but it didn't work. --Diego Bank (talk) 02:19, 17 May 2008 (UTC)

Missouri

Does the state of Missouri, with its eight adjoining states, argue against the theory? If not, perhaps an explanation would be in order? JuanFiguroa (talk) 19:29, 21 February 2008 (UTC)

No, it's quite possible to color a map of the 48 contiguous United States with four colors. [2] DanBishop (talk) 04:36, 8 May 2008 (UTC)

No, since there's no requirement that the eight states touching Missouri be all different colors -- just that any pair of states that touch be different colors. The False disproofs section of the article covers that case in a general fashion, but maybe an illustrative thumbnail map or two would be useful. -- ArglebargleIV (talk) 21:17, 21 February 2008 (UTC)

I have issue with the beginning of the article, "states of a country". US is the only country to call its regions 'states', and even that is really a misuse of the word. Perhaps 'provinces', 'territories', 'divisions' and the like. Ashleyjohnston (talk) 17:34, 2 April 2008 (UTC)

Just off the top of my head, and without doing any research, I know that India, Brazil, Mexico, Germany, Nigeria and Australia all use the word "states" to designate political subdivision of the nation. I believe Austria, Sudan and Micronesia, likewise, have states. The US is far from the "only country to call its regions 'states.'" JuanFiguroa (talk) 23:31, 5 April 2008 (UTC)

Not by Francis Guthrie?!

This site does not agree with wikipedia: http://members.ozemail.com.au/~lucire/documents/Five_colour_theorem.htm

"[...] This is called the four colour theorem, as yet an unproven mathematical curiosity, first put forward by Charles Dodgson who also wrote Alice in Wonderland."

--130.225.56.42 (talk) 07:02, 2 May 2008 (UTC)

Perhaps that's why she should stay a really expensive psych consultant and not a mathematics historian. Not surprising, Wolfram's Mathworld encyclopedic entry sides with the wiki article. Quaeler (talk) 07:41, 2 May 2008 (UTC)

Well, this is what "What is Mathematics?" By Courant & Robbins, 2nd edition, p. 247 has to say about this problem: "The problem of proving this theorem seems to have been first proposed by Moebius in 1840..." is this a mistake? —Preceding unsigned comment added by 83.130.40.64 (talk) 20:57, 3 June 2008 (UTC)

Probably, although that sounds more plausible. I believe our current sources more though. Dcoetzee 05:34, 4 June 2008 (UTC)

No, Moebius had a different problem that is sometimes conflated with the four-color problem. —Preceding unsigned comment added by 75.42.235.110 (talk) 08:37, 7 January 2009 (UTC)

downgrade to B+?

I think this article does not deserve an A class rating. It does not contain a single word about the theorem's proof. Hence the article is not "essentially complete", as the rating criteria say, in my view. If nobody is against, I will downgrade it? Jakob.scholbach (talk) 08:33, 26 May 2008 (UTC)

Oh, I see, there are some words about the proof. But still I think, the proof gets not that much attention as it should for A-class. (this is reflected by its placement in the history section, and also by the pretty little amount of actual mathematics covered in the text). Jakob.scholbach (talk) 12:27, 26 May 2008 (UTC)

To be fair, the proof is extremely complex compared to the usual level of sophistication in Wikipedia math articles - but there's no reason we couldn't attempt to construct an intuitive outline. Dcoetzee 05:20, 28 May 2008 (UTC)

I've added a basic outline of some of the proof ideas in a new section. It was informative for me and I hope it will be for others too. I'll leave the fine details of C- and D-reducibility for the brave soul who wants to try it. Dcoetzee 09:37, 28 May 2008 (UTC)

Great! Jakob.scholbach (talk) 13:38, 28 May 2008 (UTC)

Loaded word, unwarranted use

The article states that one to have "faith" in the correctness of the compiler and functioning of the hardware. "Faith" is a loaded word - usually refers to belief not based on sufficient evidence to meet criteria of logical/mathematical or scientific justification. This is most certainly not the case here. For the compiler itself, an inductive logical proof can be constructed. For the hardware, in such cases there obviously isn't sufficient evidence to warrant the claim that it didn't/doesn't work properly. This can also be tested. It's not "faith" simply because the epistemic probability is less then 100%, which it is only for analytic truths anyway - and those are vacuous.

In short, I am changing the wording to "in order to believe the proof, one also has to believe (which can be justified or not) that the compiler works as intended and that the were no other errors, such as in the functioning of the hardware, that corrupted the output." 91.67.150.18 (talk) 23:54, 27 May 2008 (UTC) MPhil

Quartic algorithm reference

I would like to see a reference to Eduard Belaga's work on an O(n^4) 4-color algorithm. I see a list of papers on the Belaga page, but none that seem related to this topic, judging from the titles alone.

How does the RSST proof utilize Belaga's work exactly? I would have guessed that Belaga somehow managed to turn the AH proof into a quartic algorithm, which isn't immediate because of some technical difficulties in the immersion reducibility part in their proof which are avoided in the RSST proof. It is not clear what there is to be utilized from that in the new proof, since the more technically straightforward RSST proof seems to "automatically" lead to a quadratic algorithm. Indeed the paper by RSST that explains their quadratic algorithm does not seem to acknowledge or refer to Belaga's work?!

143.205.82.135 (talk) 10:59, 8 August 2008 (UTC)

Robin Thomas (the "T" in RSST) answered me in an e-mail that he personally has never heard of Edward Belaga. I suspect that the information about Belaga on the Wikipedia page is plainly false. 80.121.117.151 (talk) 19:56, 9 August 2008 (UTC)

Thank you. I removed the reference to Belaga. For future reference, the sentence used to say that Roberts, Sanders, Seymour and Thomas "created a quadratic time algorithm, utilizing Edward Belaga's work to improve a quartic algorithm based on Appel and Haken’s proof". -- Jitse Niesen (talk) 20:55, 9 August 2008 (UTC)

Thank you! Still some confusion persists: it takes some effort to tweak the A&H proof into a polynomial algorithm, and a naive implementation might yield a badly exponential algorithm. Some books mention a bound of something like O(92^n) for execution time with an input graph of order n. So if the article states that the A&H proof somehow produces an O(n^4) algorithm, then a reference is needed which acknowledges the work of whoever worked this out. If it is at all possible to get a polynomial algorithm without writing an entirely new proof, just like RSST did. There might exist some paper written by Belaga in russian during the late seventies, which somebody got aware of and got inspired to edit the Four Color page to point this out, only that the precise reference got lost. If the article mentions an O(n^4) algorithm, then it ought to reference somebody, whether Belaga or others. I found Edward Belaga's e-mail, so I will ask him now what he thinks about it. Kluto (talk) 09:26, 10 August 2008 (UTC)

You're probably better placed than I do make the necessary corrections. Please feel free to do so, the "edit this page" button at the top of the article is there for a reason! I'll be happy to answer any questions you may have about the conventions here or technical issues.

Back to the matter: RSST write in Efficiently four-coloring planar graphs that "In 1989, Appel and Haken were able to devise a quartic algorithm to 4-color planar graphs from their proof of the Four Color Theorem." The list of references include their 1989 book so I guess that's where it's being done. -- Jitse Niesen (talk) 13:52, 10 August 2008 (UTC)

That sounds right. The 1989 book is most likely the proper source of an O(n^4) algorithm. Kluto (talk) 18:37, 10 August 2008 (UTC)

Generalization to higher dimensions

Out of curiosity, is there any useful generalization of this theorem to higher dimensions if we add the additional constraint that the regions must be convex? That is to say, if a convex subset of 3D space is partitioned into convex regions, can it always be colored by N colors for some fixed N such that no two regions of like color touch at a face (2D boundary)? (It seems to reasonable to permit like-colored regions to share an edge, as long as they do not touch at a 2-dimensional boundary.) It is obvious that if we allow non-convex regions, then N can be made arbitrarily high, but I have not been able to construct an example using only convex regions.—Tetracube (talk) 00:21, 29 October 2008 (UTC)

No idea. However, a short search indicates that Michal Krizak conjectures that if the regions are convex and meet face-to-face, six colours suffice [3]. Face-to-face means that two adjacent regions meet at a common face; it is the 3D analogue of edge-to-edge, as explained in tessellation. -- Jitse Niesen (talk) 10:32, 29 October 2008 (UTC)

I read the abstract; it seems that Krizek only considered polyhedra up to hexahedra, which require up to 6 colors. I wonder if this continues to hold for general polyhedra. I also wonder what the behaviour in higher-dimensional space would be like: Krizek mentions d+1 for d-simplices; I wonder how many more colors are needed for more complex polytopes.—Tetracube (talk) 17:12, 29 October 2008 (UTC)

There's an old puzzle about getting seven cigarettes to touch each other. I'm fairly certain one could get any number of convex objects to touch each other, if so then a search will probably find a solution, my quick try didn't produce anything though. Dmcq (talk) 12:47, 28 February 2009 (UTC)

But touching at a point/line does not exclude like colors, at least according to my proposed generalization. Deforming the cigarettes to touch at 2D surfaces may break the convexity requirement, perhaps?—Tetracube (talk) 20:16, 28 February 2009 (UTC)

Exclave

Because I was unfamiliar with the term, I followed the link to Kentucky bend to understand what an exclave is. Then I added a link to the word exclave in the sidebar to the article. I don't know if the term should be mentioned in the article itself. DThomsen8 (talk) 12:10, 19 March 2009 (UTC)Dthomsen

A simpler theorem

How does one proof that two colors suffice to paint the segments of an open line? --Matfan (talk) 18:28, 24 March 2009 (UTC)

Choose a segment. Paint it blue. Paint adjacent segments red. Paint segments adjacent to them blue. Repeat. Algebraist 18:34, 24 March 2009 (UTC)

Thanks a lot! This is equivalent to the parity of integers. Choose the parity of an integer to be blue. Set the parity of their neighbours red... Can something similar be done in 2D? -(mod 4) instead of (mod 2)- Or not because 2D numbers (complex) cannot be ordered? --Matfan (talk) 21:20, 24 March 2009 (UTC)

Nothing occurs to me. Do you have anything specific in mind? Algebraist 22:49, 24 March 2009 (UTC)

The sequence of numbers of colors needed, for dimension, is not the powers of two. It is instead 2, 4, ∞, ∞, ∞, ... That is, for three or more dimensions, arbitrarily many colors may be needed. So it seems unlikely that it would be possible generalize the 1d argument to 2d in a straightforward way like this. —David Eppstein (talk) 22:56, 24 March 2009 (UTC)

Well, there is a legitimate analogy to be made for n-space. Consider the infinite graph defined by letting each point with integer coordinates be a vertex, and let there be an edge between two vertices if exactly one of their coordinates differs by 1, and the others by zero. This graph (and so any subgraph of it) can be 2-colored by just taking the sum of the coordinates mod 2. Dcoetzee 03:48, 25 March 2009 (UTC)

Thank you all. What I have in mind is two situations whose solution is also min(n,4), the maximum number of colors needed to paint n regions of a map.

1) Let k=n mod 4. The maximum number of different k we can obtain from a set of n integers is also min(n,4). If the integers are consecutive, this maximum is attained.

2) The number of quadrants into which n complex numbers fall is at most min(n,4).

Can the 4-color problem be mapped into these?

The 2D version of your algorithm might look like: Choose a region. Paint the neighbours of that region (at most 3 other colors needed). Repeat for every neighbour. --Matfan (talk) 08:15, 25 March 2009 (UTC)

!!!! 4 is not enough !!!

Focius figure

You mean like this?

I'm not adding this yet to main article BUT i'm very dissapointed, since the rule of four colors no more correct, and i'm very interested how somebody proved it.

Try to color figure to the right. With love from Russia ! ))))) —Preceding unsigned comment added by Focius (talk • contribs) 13:28, 30 May 2009 (UTC)

This talk page is not here for people to throw up maps that they are insufficiently creative to properly four-color. If you think the four color theorem is invalid, please publish your disproof, but not here -- this is an encyclopedia, not a journal or a blog. (BTW, one such coloring would be, outermost square purple, square/circle blue, next ring (from the top clockwise) green yellow purple, second ring yellow blue green blue, inner dot purple.) -- ArglebargleIV (talk) 14:20, 30 May 2009 (UTC)

I sincerely hope this is a troll because there is a section called "false disproofs" which has an almost identical figure illustrating this type of error. --C S (talk) 15:07, 30 May 2009 (UTC)

"At most four"

It seems that many math-related articles suffer from the problem of ambiguous wording in English. Well, to be precise, to mathematicians the wording is unambiguous, but to the lay reader, this is not the case. The most common problem comes from phrases of the form "X can be solved/colored/etc. using at most N items". To the mathematically-clueful, this means that in the worst-case, an optimal solution requires N items (or less, depending on whether the bound is tight). However, to the casual lay reader, this is often misinterpreted to mean that all solutions (including non-optimal ones) use at most N items, which is obviously false, thereby prompting many anon editors to make incorrect changes such as substituting the phrase with "at least N", and the like.

So, for the sake of the lay reader, I suggest that this wording be changed to "only N items are needed to solve X", which gets rid of the "at most" and "at least" wording which lay readers find so confusing. Or perhaps even "theorem T says that in the worst case, only N items are needed to solve X". This phrasing is more awkward from the mathematicians' point-of-view, since the "at most N" phrasing is conventional in mathematics, but the casual reader will find it less confusing, and be less liable to attempt to "correct" what they wrongly perceive to be an error.

Comments?—Tetracube (talk) 00:59, 7 October 2009 (UTC)

Anybody who does not understand the exact meaning of at least or at most should not be

considered, since his understanding of math is too poor.

--62.0.68.57 (talk) 11:34, 31 October 2009 (UTC)

The lead states: "In mathematics, the four color theorem, or the four color map theorem, states that given any separation of a plane into contiguous regions, called a map, the regions can be colored using at most four colors so that no two adjacent regions have the same color. Two regions are called adjacent only if they share a border segment, not just a point. Three colors are adequate for simpler maps, but an additional fourth color is required for some maps, such as a map in which one region is surrounded by an odd number of other regions that touch each other in a cycle. The five color theorem, which has a short elementary proof, states that five colors suffice to color a map and was proven in the late 19th century (Heawood 1890); however, proving four colors suffice turned out to be significantly harder. A number of false proofs and false counterexamples have appeared since the first statement of the four color theorem in 1852.". That appears to answer the question. Pyrotec (talk) 11:45, 31 October 2009 (UTC)

A better formal definition?

'In graph-theoretic terminology, the four-color theorem states that the vertices of every planar graph can be colored with at most four colors so that no two adjacent vertices receive the same color, or for short, "every planar graph is four-colorable"'

Colour isn't really a mathematical concept, though you could argue that it's just a form of labelling. Still, I think we could do better. How about this?

Given a planar graph, there exists a partition of the set of nodes having no more than four parts, such that no two nodes in same part are connected by an edge.

I presume I'm not the first person to come up with this (or more or less the same thing).... -- Smjg (talk) 15:57, 21 November 2009 (UTC)

I'd add that definition as an equivalent, but I wouldn't replace the formal definition that is there. Coloring is a form of labeling, and it's good for the lay reader to be able to make the connection. Furthermore, the coloring definition is quite common in mathematical texts. -- ArglebargleIV (talk) 16:30, 21 November 2009 (UTC)

Like ArglebargleIV, I don't think this is a good idea. I think making things more abstract is exactly the opposite of what we should be doing to make our mathematics articles readable by non-mathematicians. Additionally, although there is a formal equivalence between assigning labels to objects and grouping them into partitions, they're not actually the same thing (I think there's a sense in which one is the transpose of the other), and the label assignment formalization is more standard in this area. —David Eppstein (talk) 19:13, 21 November 2009 (UTC)

I don't know what you mean about partitions being the transpose of labelling. But are you suggesting that what I said is an equivalent of the four-colour theorem, rather than an alternative formulation? Still, on the basis of what you say, maybe my formulation can be added as an "or equivalently" somewhere in that section, if we can be sure that it isn't OR. -- Smjg (talk) 22:06, 22 November 2009 (UTC)

Re transposition: a labeling can be formalized as a function mapping vertices to colors. A partition can be formalized as a function mapping colors to sets of vertices. One is the inverse relation of the other. But I don't see why adding it to the description would be likely to make things less confusing rather than more. —David Eppstein (talk) 22:39, 22 November 2009 (UTC)

Error in the Introduction

The top of the article should not state "...at most four colors", but rather "at least four colors".