Talk:Four color theorem/Archive 4

Archive 1

Archive 2

Archive 3

Archive 4

Archive 5

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)

Shoudln’t the title be “Four colors theorem” rather than “Four color theorem”? I’m not a native english speaker, but I see no reason to keep color to singular here? --92.139.121.182 (talk) 17:13, 2 September 2013 (UTC)

Considering that "four color theorem" is used about 50x more frequently than "four colors theorem" in Google scholar, I think the answer is clearly no. —David Eppstein (talk) 17:46, 2 September 2013 (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. [1] 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)

Australia has states and territories (as Canada has provinces and territories). Austria and Germany have states but of course that is, in essense, a translation from German, and in particular the term was coined when the states of those countries were far nearer autonomous. I think "divisions" is probably the nearest-to-neutral word. Si Trew (talk) 17:15, 20 April 2010 (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)

Well the article's subject is "Four colour theorem", not "Proof of the four colour theorem". Si Trew (talk) 17:31, 20 April 2010 (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 [2]. 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)

Update: I have found a paper that conjectures that every partitioning of n-dimensional space into convex n-polytopes is 2n-colorable. A proof is not known yet, but the paper examines several 3D cases, and shows some complex examples which are 6-colorable. This is suspected to be the upper limit in 3D (provided the partitions are convex, of course, otherwise there is no upper limit). Some general cases in n dimensions are examined, and it is found that the lower limit is (n+1). The upper limit is conjectured to be 2n.—Tetracube (talk) 00:10, 23 November 2012 (UTC)

This conjecture is wrong. There exist partitions of 3-dimensional space into as many convex polytopes as you like that all touch each other. An example can be given by placing many points at equal spacing along (less than a single winding of) a helix in space, and then forming their Voronoi diagram. See this paper. —David Eppstein (talk) 00:17, 23 November 2012 (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)

The python code lists all solutions with colors 0,1,2,3 and center color 0. x1,x2,x3.x4 are the four regions surrounding the center. y1,y2,y3 are the three region surrounding x1,x2,x3.

center = 0
for x1 in range(1,4,1):
   for x2 in range(1,4,1):
       if (x1!=x2): 
         for x3 in range(1,4,1):
            if (x2!=x3):
               for x4 in range(1,4,1):
                  if (x1!=x4 and x3!=x4):
                    for y1 in range(4):
                       if (y1!=x1 and y1!=x4):
                         for y2 in range(4):
                           if (y2!=x2 and y2!=x3 and y2!=y1):
                             for y3 in range(4):
                               if (y3!=x3 and y3!=x4 and y3!=y2 and y3!=y1):                           
                                  print x1, x2 ,x3, x4, y1, y2, y3

Some solutions also fullfill the condition "if (y1==x2 or y2==x1)" so that the common point may be extended to a small region. — Preceding unsigned comment added by 178.203.183.22 (talk) 08:51, 25 May 2011 (UTC)

The code may be simplified setting x1=1. The solutions for x2,x3,x4,y1,y2,y3 fullfilling the addionional condition are:

2 1 3 2 3 0/ 2 3 2 3 1 0/ 3 1 2 3 2 0/ 3 2 3 2 1 0. --178.203.183.22 (talk) 09:04, 25 May 2011 (UTC)

It is remarkable, that the lower region y3 must have the same color as the center. — Preceding unsigned comment added by 178.203.183.22 (talk) 13:50, 25 May 2011 (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". —Preceding unsigned comment added by Numberonesurvivor (talk • contribs) 20:56, 29 January 2010 (UTC)

No, it shouldn't. Any graph with four or more vertices can be colored with at least four colors, regardless of planarity: just give each vertex a different color. —David Eppstein (talk) 22:13, 29 January 2010 (UTC)

I don't follow. If a graph has N>=4 regions, it is impossible to avoid two adjacent regions having the same color if using only 3 colors (unless the graph consists of concentric circles or squares). However, it is very possible to do so if using 4 or more colors, and trivial if using N colors. It should thus say "no less than 4", instead of "at most 4". Athenean (talk) 01:07, 21 February 2010 (UTC)

A one-coloring or a two-coloring or a three-coloring or a four-coloring all satisfy "at most four colors" because one and two and three and four are all less than or equal to four. A four-coloring or a five-coloring or a six-coloring all satisfy "at least four colors" because four and five and six are all greater than or equal to four. The four-color theorem says that any planar graph has a one-coloring or a two-coloring or a three-coloring or a four-coloring. Therefore, "at most four colors" is the correct phrase to use. It is true that there are planar graphs that require at least four colors, but that's the much easier half of the four-color theorem; the difficult half is proving that every planar graph can be colored with at most four colors. —David Eppstein (talk) 03:24, 21 February 2010 (UTC)

Four Colors Do Not Suffice

See "Four Colors Do Not Suffice", Hud Hudson, The American Mathematical Monthly, Vol. 110, No. 5 (May, 2003), pp. 417-423, http://www.jstor.org/stable/3647828.

Hudson constructs a map requiring six colors by using regions similar to the topologist's sin(1/x) curve, which have finite area but infinite perimeter. The regions are all bounded and path connected and share a common boundary line segment. So, six colors are needed. Each region union the common boundary is not path connected. Hudson also shows that for any n, there is a map that requires at least n colors.

Hudson thus disproves the following two statements:

• Four colors are sufficient to color any map drawn in the plane or on a sphere so that no two regions with a common boundary line are colored with the same color.

• Four colors are sufficient to color any dual graph (of a map drawn in the plane or on a sphere) so that no two vertices connected by an edge are colored with the same color.

Appel and Haken actually proved the following:

• Four colors are sufficient to color any planar graph so that no two vertices connected by an edge are colored with the same color.

David Marcus (talk) 15:24, 16 September 2010 (UTC)

What Gonthier proves is that "The regions of any simple planer map can be coloured with only four colours, in such a way that any two adjacent regions have different colours", where "a planer map" is "a set of pairwise disjoint subsets of the plane called regions and "a simple map" is "a map whose regions are connected open sets", and where "two regions of a map are adjacent" if "their respective closures have a common point that is not a corner of the map" and "a point is a corner of a map" if and only if "it belongs to the closure of at least three regions". Importantly the "corners of a map" need not be isolated points and can even form line segments. In Hudson's example, all the regions would technically be considered non-adjacent because all the border points are shared with at least three regions, and therefore could all be coloured with one colour. Though Hudson's example is a good illustration that maybe the technical statement of the four colour theorem doesn't live up to our informal expectations. In any case, the statement of the theorem was wrong in the first paragraph. I've corrected it. 81.56.46.96 (talk) 22:09, 2 May 2011 (UTC)

It seems to be wrong again. A reference for a correct statement is "Formal Proof---The Four-Color Theorem", Georges Gonthier, Notices of the AMS, Vol. 55, No. 11 (December, 2008), pp. 1382-1393. Definitions: A planar map is a set of pairwise disjoint subsets of the plane, called regions. A simple map is one whose regions are connected open sets. Two regions of a map are adjacent if their respective closures have a common point that is not a corner of the map. A point is a corner of a map if and only if it belongs to the closures of at least three regions. Theorem: The regions of any simple planar map can be colored with only four colors, in such a way that any two adjacent regions have different colors. David Marcus (talk) 16:22, 5 December 2011 (UTC)

OK, changed first paragraph to match this definition, and provided full definition in the footnote (primarily since terms such as 'closure' would be mysterious to many readers, I suspect...) LouScheffer (talk) 18:49, 5 December 2011 (UTC)

While I am not a mathematician, I strongly suspect an alternative statement, that matches intuition better, would be:

• Four colors are sufficient to color any map drawn with connected regions of finite perimeter in the plane or on a sphere so that no two regions with a common boundary line are colored with the same color. LouScheffer (talk) 13:24, 17 September 2010 (UTC)

I don't know how to prove your statement nor do I have a counterexample. However, it isn't the way the four color theorem has been stated all these years. Hudson notes that the two statements he disproves are the way the theorem is stated in Satty and Kainen's book. As for whether your statement matches intuition better, that depends on one's intuition. David Marcus (talk) 03:25, 29 September 2010 (UTC)

Do we need "The island of five colors" to be added to "In fiction" section?

Martin Gardner wrote a short story about 4 color theorem where the protagonist had actually marked the lands of four tribes with the paint, after he was told that these 4 tribes had their territories devided in the way that disproved the theorem. Here is the link http://kasmana.people.cofc.edu/MATHFICT/mfview.php?callnumber=mf100 —Preceding unsigned comment added by 95.58.129.147 (talk) 15:53, 11 October 2010 (UTC)

World map

Why isn't this map included in the article? Matthewedwards :  Chat  02:55, 30 November 2010 (UTC)

Including white, I count five colors in this map.—GraemeMcRae^talk 17:20, 3 December 2010 (UTC)

But the white doesn't count as area. Seeing as how this is a graph problem, you can have a disconnected graph, consider G = ({a,b}, {}). The corresponding map would need to a and b to not share a border, hence, ocean or no-man's-land. —Preceding unsigned comment added by 129.177.190.112 (talk) 14:40, 18 January 2011 (UTC)

If you include white as a color, then some of the land-locked regions would be white. Thus, one of the other colors would not be present. Xtarka (talk) 18:46, 30 March 2011 (UTC)

Considering that position, then this USA map should not be included in article. Shadowxfox (talk) 20:21, 1 April 2011 (UTC)

I'm quite convinced the four color theorem is nonsense. Starting with a larger map like the united states or the world map, it is easy to construct a map that is at least much more difficult to color using only four different colors. For example one always can include the surrounding like the water as additional countries. Of course a country having less than four neighbours can always be colored by a fourth color. In such a case two countries might by unified to make it more difficult. A common point of more than three countries may always be extended to an additional country. But one thing is remarkable. The average number of neighbours is always smaller than six, at least I believe so. Who disagrees? --178.203.183.22 (talk) 09:02, 30 April 2011 (UTC)

Sorry. I was misstaken. The theorem can be proven showing that in case of one county with four or five neighbours, the colors of the neighbouring countries always can be changed in a way, that only three different colors occur (Alfred Kempe). Therefore a counterexample having the lowest possible number of countries can not have a country with less than six neighbours. — Preceding unsigned comment added by 88.152.231.121 (talk) 16:06, 8 September 2012 (UTC)

Disproof

Think of a number of smaller countries, let us call them 1,2,3,4, ..., in one line from east to west. North of the countries the 1,2,3 and 4 there is a country N_A with borders to 1,2,3,4, north of 5,6,7 and 8 is a country N_B and so on. South of country 3,4,5 and 6 there is a country S_A, south of 7,8,9,10 there is a country S_B and so on. There are common points of 4,5,N_A and N_B and of 6,7,S_A and S_B. Such common point are thought to be extended to a smaller country having borders to 4,5,N_A und N_B. One see easyly, that the set of countries {5,6,7,8}, {7,8,9,10}, {9,10,11,12} can not be colored with only two different colors, because of the expanded countries. So they must be colored with three different colors. But this also doesn't work. --178.203.183.22 (talk) 11:25, 11 May 2011 (UTC)

Sorry, I was mistaken. It is possible to color the map using three diffent colors for the sets {1,2,3,4}, {5,6,7,8}, {7,8,9,10}, ... AB-CA+BC-BD+AB+CA-178.203.183.22 (talk) 15:45, 11 May 2011 (UTC)

Don't waste your time trying to find a counterexample. This result has stood for centuries, I believe, and is completely verified nonetheless. - 96.255.65.6 (talk) 07:43, 1 April 2012 (UTC)

Discussion of Possible Disproof

When I heard about this in maths, I instantly thought of a scenario, but it arouse some dispute in my mind.

I would like input as to whether you agree that a central point does infact validate the disproof.

• 
  This disproof works on the basis that the center point constitutes two colours touching.

If you look at the statement of the theorem you'll find that two regions with the same colour which touch at a vertex is allowed, its only the case when they touch along an edge which is prohibited. In your example purple could be switched to blue and you would get four colours, indeed you could switch yellow to red to get 3 colours.--Salix (talk): 09:27, 11 December 2010 (UTC)

Map coloring

Map coloring redirects to Four color theorem. It should be an article by itself, obviously linking to Four color theorem. Map coloring is much more than coloring planar graphs in at most four colors.

I agree, and constructed an initial map coloring article that discusses many of the issues with picking colors for maps (and of course refers to the four color theorem.) LouScheffer (talk) 15:01, 27 July 2011 (UTC)

Four color theorem as applied to cell tower placement

Diagram showing circles (cell tower range) along a highway.

The four color theorem has been applied to cell tower placement; see here and search for "four color mapping theorem". Cell channel spectrums -- each one coming from a different tower -- can be thought of as colors, and only four are needed in flat places such as New Jersey.--Tomwsulcer (talk) 03:13, 19 April 2012 (UTC)

That does not look like a reliable source and its identification of planar maps with overlapping disks, solely because both types of things can be called two-dimensional, does not fill me with confidence in its mathematical rigor. —David Eppstein (talk) 03:42, 19 April 2012 (UTC)

It indicates to me that the four color theorem is of interest in the subject of cell tower placement. According to WP's rules about sources, the source is somewhat light since it is a blog; however, as you know, which sources we apply is a judgment call, and according to my personal judgment, it is a good source on this issue (I do not see any biases or reasons to discount it.) And blogs have been used elsewhere when appropriate. I did not make up the idea; it is not original research as was claimed when the addition of my diagram of cell tower placement was reverted. And I continue to believe that the issue of cell tower placement is a valid instance of one of the few real-world applications of the four color theorem.--Tomwsulcer (talk) 13:56, 19 April 2012 (UTC)

It is easy to place five cell towers so that they all overlap each other. How does the four-color theorem apply in that case? What are the regions to be colored? —David Eppstein (talk) 15:13, 19 April 2012 (UTC)

My understanding (which may be imperfect here -- I am trying to follow the logic correctly -- please bear with me -- I am not an expert in anything unfortunately) is that each cell tower is like the center of a circle or sphere -- it broadcasts up to a fixed distance (the radius) so that a car or person with a cell phone within that radius can pick up the signal, and have a two-way conversation, essentially a walkie-talkie radio transmission between the cell phone and the tower (which, in turn, relays the conversation over the phone network or satellites or whatever it does). If a person/car using the cell phone moves to a different area, the cell phone system has to pick up the fact that the customer is moving, and hand off transmission duty to the second tower, that is, the cell phone company must cease transmitting from the first tower, and begin transmitting from the second tower. This handoff can not happen if both towers are using the same broadcast channels (if I understand this correctly -- I am kind of piecing together what the logic is -- I may be wrong about this) -- tower A has to broadcast on one channel, and tower B must use a different one. And, by analogy with the four color theorem, the broadcast channels are like colors -- each color is a different broadcast channel. So adjacent towers (circles, spheres) can not be the same color, or broadcast channel. For the cell phone company, it might be prohibitively expensive if it had to use up numerous different channels, that is, it can minimize costs and maximize profits by using the fewest number of different channels, that is, it is cheaper (and possibly simpler?) for it to use as few channels (or colors) as possible. And the four color theorem instructs cell tower placement people that they only need four channels to spread out their towers in a plane (I realize it's 3-D but for all practical purposes we can think of the problem as a plane). I came across this idea somewhere while working on the bio of a cell phone scientist, or maybe somewhere else (I do not remember exactly -- but I think there are at least two sources on this -- I can only find one now) and I can followup with him to ask him about this. The cell phone scientist is mathematically oriented like yourself and can perhaps enlighten me about whether this is a genuine application of the four color theorem, and if the assumptions are correct, so I will try to ask him when I see him next.--Tomwsulcer (talk) 15:59, 19 April 2012 (UTC)

My feeling is that if you're this vague on what the mathematical theory actually is, you shouldn't be trying to add it to a mathematics article here. —David Eppstein (talk) 16:28, 19 April 2012 (UTC)

Noted. My feeling is that it is a mistake to shut oneself off from differing viewpoints. None of us knows everything; knowledge (even math) is uncertain; please try to keep an open mind. I am not vague on the mathematical theory as it relates to this example but what is unclear to me are a few assumptions underlying how cell towers work as a system, and I will try to find this out. In deference to your expertise, I will heed your suggestion and keep the cell tower diagram out until I get more information. :) --Tomwsulcer (talk) 17:35, 19 April 2012 (UTC)

Update. I spoke with a cell tower scientist and mathematician who runs a division at Alcatel Lucent about the whole issue of applying the four color theorem to the task of intelligently placing cell towers along a highway. He knew about the four color theorem, and he said "it's possible". He said that some adjacent cell towers did indeed use different frequencies; that is, as a user in a car drives from the area of cell tower A, to the area of cell tower B, the handoff goes from one frequency to another frequency (as if they were different "colors"). But, he said there were instances in which the frequencies were the same on adjacent towers. So a person in between tower A and tower B might be talking via both towers simultaneously, and the cell phone company has some way to handle this using codes, somehow sorting out the timing and signals so that conversation was comprehensible. "It's complex" he said. Somehow, all this technology works. So I figure I will merely post this here, and let others decide whether to add anything to the four color theorem article; if I come upon new information, I will post it here too.--Tomwsulcer (talk) 12:13, 30 April 2012 (UTC)

Relations

related to the same problem: you cannot connect 5 dots to each other on a 2d plane without crossing one of the lines, or placing the 5th point on a line, which invalidates the result.

extrapolating this info, it can be seen that in 1d space, 3 colors are needed (if only the sides of the lines count as adjacent, not the points). therefore in 3d space, 5 colors should be required to color a map.

furthermore, there is a simpler visual proof than a circle. it is best visualized as a triangle within a triangle, with one of the triangles being segmented into 3 areas. this is consistent with other 2d geometric theories. 64.250.81.218 (talk) 00:33, 28 April 2012 (UTC)

In 3d space, many more than 5 colors may be required: there are maps (even having all regions be convex polyhedra) with arbitrarily large numbers of regions, all adjacent to each other. —David Eppstein (talk) 00:37, 28 April 2012 (UTC)

have any examples? interesting. actually, even thinking back to my own example, in 1d space the lines can only be ordered end-to-end, since making them adjacent would extend it to a 2nd dimension. curious about these 3d maps. 64.250.81.218 (talk) 00:45, 28 April 2012 (UTC)

well, i can visualize it at least, seems 1d = 2 colors (most likely just 1 if vertices are not counted), 2d = 4 colors, 3d = infinity? still hard to wrap head around this, and would require proof if you have any ;p 64.250.81.218 (talk) 00:53, 28 April 2012 (UTC)

An example. See in particular figure 1 of that paper. —David Eppstein (talk) 01:11, 28 April 2012 (UTC)

nice, thanks. it seems the 2 issues are related. ie: you can connect infinity objects using curved lines in 3d space to each other without crossing any other lines. if they are straight lines however, you can only connect 5 objects in 3d space. simple analogy here: if you have 10 objects, each with 9 pieces of string attached, connecting them to all other objects. however, in 2d space, even with splines, you cannot connect more than 4 objects without crossing any lines. same for straight lines in 2d. seems like what matters here is whether (or the amount of objects) than can be fully meshed. (coming from a networking background). ie: like a fully meshed/routed network. 64.250.81.218 (talk) 03:31, 28 April 2012 (UTC)

Please read my article I write recently and give your precious opinion, Thank you a great deal! http://www.paper.edu.cn/index.php/default/releasepaper/content/201207-15 — Preceding unsigned comment added by Yuqiu54 (talk • contribs) 06:10, 4 July 2012 (UTC)

Converse?

The Android game Untangle states this in its description:

For the more mathematically minded, the colors show that every graph is 3- or 4-colorable, which implies that it is planar and can be solved.

Is this implication true, or is it something that the game author made up? Essentially, if we consider the colourable regions as nodes of a planar graph, then this is claiming what can be considered a converse of the four-colour theorem: that every 4-colourable graph is planar.

But is this the case? It would be nice if we can find some information on the matter to add to the article. — Smjg (talk) 00:21, 25 July 2013 (UTC)

No it is not true, not even almost. Even being 2-colourable doesn't imply planarity, consider K_3,3. McKay (talk) 04:41, 25 July 2013 (UTC)

What was so wrong with Kempe's Chains

Kempe's chain method works on almost all planar graphs. Kempe's method failed to properly four color a very specific coloring of a specific graph. It seems that this is the only reason that Kempe was rejected. Are there any more compelling reasons for this decision?

Jillbones (talk) 06:27, 2 July 2013 (UTC)

Even one failure and it's not a proof. —David Eppstein (talk) 06:33, 2 July 2013 (UTC)

How about "failure with recovery"?

See for example http://www.academia.edu/1179130/The_Four-Color_Map_Theorem_Kempes_Fallacious_Proof_Repaired_

Further results can be found in the first 6 pages of my paper at arXiv : http://arxiv.org/abs/0903.4108

Icahit (talk) 07:17, 9 September 2013 (UTC)

Arxiv is considered a self-published source, because there is little editorial control on the quality of its papers. To add it to this article, it would need to be published in a reputable mathematics journal. —David Eppstein (talk) 07:30, 9 September 2013 (UTC)

Bad sentence

"However, the unavoidability part of the proof was verified in over 400 pages of microfiche, which had to be checked by hand (Appel & Haken 1989)." -- Microfiche is not a verification method but a storage medium. I don't have A&H handy so I can't check what they actually say, but this sentence needs editing to make it meaningful. McKay (talk) 04:47, 3 September 2013 (UTC)

Bad Troll. Learn 2 English. — Preceding unsigned comment added by 205.221.255.62 (talk) 17:09, 27 December 2013 (UTC)

A minor thing

In the leading section: "Additionally, any map (regardless of whether it is a counterexample or not) must have a portion that looks like one of these 1,936 maps." Actually not "any map" but any map that satisfies some necessary conditions for being a minimal non-4-colourable triangulation (such as having minimum degree 5). The description later might have this problem too. McKay (talk) 03:25, 21 February 2014 (UTC)

OK, I changed the wording in the lead section to account for this. Opinions on whether this change is an improvement are always welcome. LouScheffer (talk) 12:59, 21 February 2014 (UTC)

OK, fixed the later wording too. Comments welcome. LouScheffer (talk) 13:05, 21 February 2014 (UTC)

n dimension

In n dimension, is there a "2ⁿ color theorem?"

For example, on a line, there is a 2 color theorem, in space, there is a 8 color theorem. — Preceding unsigned comment added by 101.10.10.197 (talk) 16:41, 26 July 2014 (UTC)

No. It is possible to find a subdivision of three-dimensional space into convex regions all of which touch each other. For instance, take the Voronoi diagram of any discrete subset of points on the moment curve. —David Eppstein (talk) 18:20, 26 July 2014 (UTC)

World map examples

Although a world map can be colored with four colors, as the examples show, it is not the best example because it does not strictly satisfy the assumptions of the theorem, namely that a single region can't have disjoint segments like some countries do. But do we really have a better alternative?--Jasper Deng (talk) 20:44, 28 July 2015 (UTC)

A stronger conjecture

Is it true that if a graph (can be either planar or non-planar) does not contain a sub-graph homeomorphic to K_n (the complete graph on n vertices), then it can be painted with at most n-1 colors? For n=1, 2, 3, it is easy to prove, and Paul Dirac proved that it is true for n=4, but is it true for all natural number n? If the n=5 case is true, then it will imply the four color theorem, since a planar graph can't contain a sub-graph homeomorphic to K₅. — Preceding unsigned comment added by 101.14.225.52 (talk • contribs)

This is Hajós' stronger version of the Hadwiger conjecture. It is false: for n-vertex rndom graphs the biggest complete subdivision has a number of vertices proportional to the square root of n but the chromatic number is proportional to n/log n. See the Hadwiger conjecture article for details. —David Eppstein (talk) 17:24, 8 August 2015 (UTC)

Congo

The one true 4 color map (http://upload.wikimedia.org/wikipedia/commons/a/a9/World_map_colored_using_the_four_color_theorem_including_oceans.png) is actually wrong, the Congo and Sudan are both yellow. I think this map is just wrong and not planned out properly. There's no way to fit in South Sudan, or to split up Czechoslovakia. KarstenO (talk) 16:13, 16 May 2015 (UTC)

I'm taking this map out of the article. As KarstenO points out, it shows two adjacent countries in Africa both in the same color, yellow. Loraof (talk) 19:31, 18 August 2015 (UTC)

Algorithm?

(1) Given a map, is there a known algorithm to determine a valid coloring in polynomial time (or otherwise) in the number of regions? [It's mentioned in the section "simplification and verification".] Loraof (talk) 20:08, 18 August 2015 (UTC)

(2) Given a map, is there a known algorithm to determine in polynomial time (or otherwise) whether the map can be colored using just three colors or whether four are required?

If these are known, or are not known and are objects of research, it might be worthwhile to mention that in the article. Loraof (talk) 19:48, 18 August 2015 (UTC)

(2) is known to be NP-complete. It's mentioned at Graph coloring#Computational complexity but should probably also be included in this article. —David Eppstein (talk) 20:45, 18 August 2015 (UTC)

Surely there are infinite maps that require four colours?

Hello,

Is this the right place to discuss an article? I am confused by the assertion that there are precisely 1,936 maps requiring four colours. As far as I can make out, there are three principal four colour maps, two of which can have a slight variation, and two of which can be modified to make an infinite number of maps. Thus there are infinite maps requiring four colours.

A friend of mine suggested that there were 1,936 *classes* of map. Is that correct? I cannot think of that many classes of map. What are they? Where can I see them?

Edmund

Exxxz (talk) 14:29, 23 December 2015 (UTC)

There were 1936 cases in the case analysis of the proof. There are as you say infinitely many planar graphs, most of which were not used as cases in this case analysis. —David Eppstein (talk) 17:17, 23 December 2015 (UTC)

Why is the number 1,936 significant?

I feel that the article needs editing. Any region surrounded by an odd number of other regions (apart from one) requires four colours, and any region divided into an odd number of sectors, surrounded by a one region ring requires four colours. Am I being obtuse, or is the number 1,936 actually significant? I make, as I wrote, that there are three principal four region maps, two of which can have a slight variation, and a different two of which (see above) can have more regions added, making two lots of infinite maps requiring four colours. Can someone please explicate what 1,936 maps have to do with anything?

Ed Z

Exxxz (talk) 16:15, 31 December 2015 (UTC)

Did you read the answer to almost the same question that you posted immediately above this one? —David Eppstein (talk) 19:13, 31 December 2015 (UTC)

Surely these are all the types of map?

• 

What I am trying to work out, is what other principal four colour maps are there? These are all that I can think of...Exxxz (talk) 12:37, 5 January 2016 (UTC)

Exactly how many classes of maps requiring four colours are there?

As in my contribution including my .pdf, as above, are there more 'types' of map that I'm missing? If this is not the place to discuss the issue in general, then where should I go? Exxxz (talk) 14:35, 13 January 2016 (UTC)

In the proof of the theorem they have to test 1,476 reducible configurations. This indicates there are considerably more classes that the ones in our diagram. --Salix alba (talk): 22:20, 13 January 2016 (UTC)

Other principal four colour maps?

Hello Again, Hmm... Could someone actually post, or point me in the direction of the presumably vast number of classes of map that I am missing? Obviously one could add any number of random blobs to my maps, but I can't think of any more basic types of map other than those in my .pdf... Exxxz (talk) 18:31, 22 January 2016 (UTC)

Dude. This iis the sixth time you have opened a new section here to ask, essentally the same question. Have you even read any of the answers from the other five times you asked it? —David Eppstein (talk) 18:45, 22 January 2016 (UTC)

Exxxz, the four-color problem is not "find a map that requires four colors rather than three", but "show that no map requires FIVE colors". This is why your list of patterns isn't complete. For example, consider the map of a dodecahedron -- locally, it has pentagons surrounded by five other regions, as in one of your examples; but the fact that each such six-region neighborhood can be four-colored doesn't tell you whether that coloring can be extended to the rest of the map. (In fact, your first three patterns and their variations, besides being equivalent to each other, are not even among the 1936, as I understand it -- it's not hard to show that a minimal counterexample would have no regions with fewer than five neighbors.) Joule36e5 (talk) 02:34, 18 February 2016 (UTC)

Contradiction between two Wikipedia entries/sections/articles

The article "Francis Guthrie" states "At the time, Guthrie was a student of Augustus De Morgan at University College London" This is the second sentence, the first sentence referring to nobody else. Thus the Guthrie referred to is Francis Guthrie who is stated to be a student of De Morgan.

On the other hand the current article "Four Color theorem" states "At the time, Guthrie's brother, Frederick, was a student of Augustus De Morgan"

Both articles cannot be correct. — Preceding unsigned comment added by BrianAstle (talk • contribs) 16:16, 21 February 2016 (UTC)

I've edited Francis Guthrie to agree with this article, based upon this article. Paul August ☎ 15:09, 22 February 2016 (UTC)

I believe that is correct. McKay (talk) 05:35, 23 February 2016 (UTC)

Three color theorem

Is there's a possiblity of maps only having three colors? Has limitations? — Preceding unsigned comment added by 46.130.138.25 (talk) 18:19, 11 March 2016 (UTC)

If there are no points shared by only three regions (Grötzsch), or even if there are up to three such points (Grünbaum), then the map is 3-colorable. There are also some unproved conjectures about 3-colorability. I don't know if this is worth adding to this article, or perhaps some related article. (Grötzsch is already in the see-also section of this article.) Joule36e5 (talk) 01:59, 12 March 2016 (UTC)

Correct Formulation of Statement for Four-Color Problem

I am one of those who is not satisfied with a computer 'solving' the 4-Color Problem; however, my reason is simply that the 'proof' doesn't teach us anything. I've also tried to 'outwit' the 4 color constraint many times over many years, and something strikes me about the whole idea: namely that I can see why it's true; I just can't prove it. I've wondered for some time now if it would help to word (as well as think of) the problem in the following way:

    "On any effectively 2 dimensional surface such as a map or a globe, the greatest number of closed figures which can be drawn in such a way that each one touches every other one along a straight or curved side, is 4."

This makes the problem not so much about colors as about geometry and topology. The fourth shape always cuts off one or more of the others, so that additional shapes cannot touch one or more of the first 3. You can only escape this by veering into extra dimensions, or folding the paper (like hyperspace.) I may not be adequately describing this - and I certainly don't have the skills to prove it, but it is definitely a fundamental constraint, and that it what makes the 4-Color Theorem true.

Richard Deese 24.129.75.83 (talk) 09:46, 29 April 2016 (UTC)

That is a different and much easier problem, a form of Kuratowski's theorem. But it is easy to construct plane maps that require four colors despite not having four mutually-touching shapes, so the hard part of the four-color theorem is proving that this doesn't happen with one more color (requiring five colors despite not having five mutually-touching shapes). —David Eppstein (talk) 15:53, 29 April 2016 (UTC)

Finally, Proved

(Any map we consider as a graph)
1. If graph has two vertices, we use two colors.
2. Adding another vertex, and joining it with each existing vertices, it's necessary to use a third color.
3. Adding another vertex more, and joining it with each existing vertices, it's necessary to use a fourth color.
4. If add another vertex more, we CAN NOT join it with ALL ALREADY JOINED WITH EACH OTHER, four vertices — because if we could to do this, we'll get FULL K5 GRAPH, that is NOT PLANAR.
4.1. If we have almost full K5 graph (without one edge), we use same color for two NOT JOINED vertices, still using 4 colors for full map.
4.2 If join two these vertices, we get non planar graph, not possible on plane.

So, we does not ever have necessity to use 5th color — 4 is always enough.

Ващенко Всеволод (talk) 21:30, 29 January 2017 (UTC)
Origin: Проблема Четырёх Красок
(I'm sorry if made some grammar mistakes, english is not native)

You are just making the same error as someone else made in the previous section on this page. McKay (talk) 02:34, 30 January 2017 (UTC)

No, it's not. Show me, where you see that error and explain, please, and i'll show you, that you're wrong. Ващенко Всеволод (talk) 09:34, 30 January 2017 (UTC)

Your argument shows (or rather asserts) that there can be no five-vertex complete graphs in a planar graph, but this is known and easy. It doesn't show that four colors suffice, because there are graphs requiring five colors that do not include a five-vertex complete subgraph. In any case, this talk page is the wrong place for this. We are here to discuss improvements to the article based on reliable sources. You have no published source for this material, so there is nothing we can include. —David Eppstein (talk) 11:34, 30 January 2017 (UTC)

"there are graphs requiring five colors that do not include a five-vertex complete subgraph" — we talking only about planar graphs, because it is basic condition for map. Ващенко Всеволод (talk) 12:05, 30 January 2017 (UTC)

Please discuss this elsewhere. As David Eppstein said above this is not the appropriate place for such discussions. Paul August ☎ 13:00, 30 January 2017 (UTC)

Why? I'm writing not on the main page, but exactly in place where can discuss. And because I have the real proof. In addition to my words of proof: every region of map, that needs four colors, is reducable to K4, and some cycled graphs. Point is: we can reduce cycled graph to just 3 vertices: first, second and one possible vertex, that closes the circle. All vertices between them has 2 colors, that repeats two colors of two first vertices, so for now we forget about it. So we get 3 colored K3 graph (triangle), and three places for possible existing another vertex: inside graph, outside it And inside of any vertex (that also is territory). If outside, maximum we get graph K4, that is reducable to 3 triangles (and do the same proof for each); If inside, we get also 3 triangles; If inside an another territory, you can check by yourself, that it's impossible to make something, that is not divided by triangle or cycled chain (proof is valid for all triangles and cycled chains on map) Ващенко Всеволод (talk) 17:40, 30 January 2017 (UTC)

Because, as David has already told you, the purpose of article talk pages are to discuss proposed changes (based upon reliable sources) to the article, see WP:talkpage. Paul August ☎ 17:47, 30 January 2017 (UTC)

So, can you help me? What is the place with somebody, who needs my obviously correct proof, that was not refuted by Wikipedia users? Ващенко Всеволод (talk) 19:22, 30 January 2017 (UTC)

I don't know, but not anywhere on WIkipedia. Paul August ☎ 19:29, 30 January 2017 (UTC)

Try writing it up as a paper and putting it on arxiv.org. Then invite other mathematicians to tear the proof to shreds. That's a good place to start, I think. Marchino61 (talk) 05:11, 2 February 2017 (UTC)

No, don't. ArXiv doesn't want crank mathematics papers, putting on arXiv is not a way to get a publication that can be used as a reliable source here, and in this case what is needed is not that other mathematicians see and appreciate the proof. What is needed is that the original poster understand that this line of approach to the problem is both well-trodden and inadequate. —David Eppstein (talk) 11:34, 2 February 2017 (UTC)

David is correct: it is definitely not appropriate for arXiv.org. But it can be asked on WP:Reference desk/Mathematics and someone might be kind enough to explain your error. But you need to listen to them; we have seen your claimed proof a hundred times and it remains just as false as ever. McKay (talk) 01:44, 3 February 2017 (UTC)

Origin of the four color theorem and Mobius

In the text, it is written that "Möbius mentioned the problem in his lectures as early as 1840.[4] " See the following paper, which states that there is no evidence that Möbius mentioned this problem.

The Origin of the Four-Color Conjecture, http://www.jstor.org/stable/228109 Sangil (talk) 13:44, 3 February 2017 (UTC)

Four colour maps... with five colours?

Am I the only one seeing five colours in the "four colour" geographic maps? Surely the ocean is also part of the map. The fact that we know from personal experience that that area isn't a country shouldn't matter. The maps can (should?) be rendered without using a 5th colour for the ocean(s). 85.138.248.47 (talk) 03:10, 19 July 2014 (UTC)

You are correct. The five-colour map of the world has no encyclopedic merit in the context of this article, because it does not address a condition within the scope of the theorem in which a fifth colour would be required. You have correctly observed that the ocean is a region subject to the conditions of the theorem, and it should be coloured with one of only four colours. The irrelevant map should be removed in order to restore the integrity and clarity of this article. Unfortunately the accompanying text hopes to excuse an illicit fifth colour so as to avoid having inland countries share a colour with the ocean, but we must observe that the scope of the theorem has no relation to this arbitrary and superfluous preference. If a person wants to add restrictions for how pairs of regions may be coloured, and if they want to use additional colours to satisfy those restrictions, that person has stepped outside the bounds of the four-colour theorem. Inclusion of the map is therefore a surprising embarrassment that gives an amateurish touch to an otherwise strong article. I can understand if an over-eager contributor invested a lot of time to produce the map without understanding the article, but I can't understand the insufficient editorial discipline that keeps the invalid contribution in place. The map contributes nothing and only fosters confusion among readers who are new to the topic.76.202.215.28 (talk) 09:03, 20 November 2017 (UTC)

Diagrams

More vivid colors.

There are points here where four shapes intersect.

I like the beautiful colors of the diagrams in this article but at the same time I see areas where improvements can be made:--Tomwsulcer (talk) 13:56, 19 April 2012 (UTC)

United States diagram. I substituted the map of US states with a more vivid example; still, I think the US as an example of the four color theorem is problematic for three reasons: (1) Alaska & Hawaii are islands (2) four western states intersect in a single point, meaning we have to deal with this by either (a) explaining that New Mexico and Utah "don't touch" (I think they do btw) because they only share a single point or (b) use a different map or (c) find a way to use only four colors (I found a way). Still, I think using a different country, such as France (problem: Corsica) or Germany (better in my view) is a better alternative for us. In addition, many users here in WP complain there is an over-emphasis on things related to the United States.--Tomwsulcer (talk) 13:56, 19 April 2012 (UTC)

The US diagram would be better with New York and Rhode Island in different colors, e.g. with one of them dark red. The two states share a water border in Block Island Sound. — Preceding unsigned comment added by 207.38.206.161 (talk) 20:16, 13 January 2018 (UTC)

Top diagram. The first diagram, at the top of the page, while beautiful to look at, has four shapes intersecting in one point. I am dissatisfied with the explanation that the four shapes don't touch because they only touch only on one point -- in my view, the upper left and lower right areas are adjacent and touch, regardless of any attempted explanation at what adjacent means; and, as such, it does not constitute a good example of the four color theorem. It does not seem to be mathematically rigorous to have that diagram as an example of how the four color theorem is applied.--Tomwsulcer (talk) 13:56, 19 April 2012 (UTC)

Responding to wiki flag dated March 2018 regarding length of lead section

A first-time contributor, please be gentle.

While the mathematical and cartographic aspects of this topic are inexorably entangled, perhaps casual readers would best be served by a disambiguation? Reading the Talk page suggests that much of the interest here is genuinely mathematical. Separation into two articles with liberal cross-references could help filter the content for readers.

The existing lead section strikes this reader as awash in commas, making the "read" longer even if the text is not. Why not, "The four color theorem (or four color map theorem) in mathematics states: given ...". The last sentence of paragraph one could also be eliminated or relocated by footnoting the first use of adjacent.

Welcoming feedback, --WFinterests (talk) 21:39, 31 March 2018 (UTC)

What other article than the mathematical one do you have in mind? I think if you strip out the mathematical content there is little or nothing to say about cartography. —David Eppstein (talk) 21:50, 31 March 2018 (UTC)

I agree with David -- "real" cartography has never been concerned with color minimization; this is only of mathematical interest. Some parts of the article are phrased in terms of cartographic maps just to give the layman something to relate to, just like Ramsey's theorem is commonly phrased in terms of guests at a party. Joule36e5 (talk) 22:17, 31 March 2018 (UTC)

Not sure I understand what exactly WFinterests is suggesting above. But does anyone have any thoughts on the lead length being tagged "too long" here? Paul August ☎ 14:24, 1 April 2018 (UTC)

Hi, @WFinterests, David Eppstein, Joule36e5, and Paul August. Firstly, welcome, WFinterests - it's good to have you aboard!

I was the one who tagged the lead as too long, and did so simply due to sheer size of it. A lot of the material in it is valid - the importance of the theorem is, among other things, due to it being the first to be proved by computer - but there is a lot of detail, especially about the computer proof, that is better situated in the article itself, with the lead edited down to more of a summary. I tagged it instead of making the change, though, as it was something I didn't have time to do at that point, as it'd ideally need cross-checking that items removed from the lead were still elsewhere in the article (which it would need to be, based on the advice in the guidelines for lead sections).

My recommendations:

• The definition of the theorem and subsequent explanation of what "adjacent" means in context could be reworded to be a simpler introduction; as WFinterests points out, the over-use of commas can make it difficult for the reader to follow (the opening sentence alone is split by no less than six commas). My thoughts are that it could be first introduced as a statement providing more of a lay introduction, and then the specifics detailed in the sentence that follows it. For example, "In mathematics, the four color theorem, or four color map theorem, is a theorem that describes the number of colors needed on a map to ensure that no two regions that share a border are the same color. Specifically, it states that after separating a plane into contiguous regions to produce a "map", no more than four colors are required to color the regions of the map so that no two regions sharing a boundary line have the same color". This could potentially be followed immediately by the third paragraph discussing three- and five-color maps, as well as the false proofs and counterexamples since the first statement from De Morgan (due Guthrie).
• The relative disinterest of cartography in the theorem isn't mentioned after the lead ("cartograph*" appears only three times in the article, and all in the second paragraph of the lead). Given that the theorem originates with a cartographic observation by Guthrie, this is perhaps worth introducing in the history section, or in a subsequent section. I'm not sure that there is enough material for an article of its own.
• As mentioned previously, Appel and Haken's computer proof has too much detail in the lead, and really should just be summarised, with the fifth paragraph condensed into the fourth. This could also emphasise the importance of the theorem and computer-assisted proof in the history of mathematics with regards to use of computers (including the controversy over the status of the early proofs, given their length and difficulty in proving by hand).

I am more than happy to discuss any other amendments, but I feel that a bit of editing could tighten up the lead nicely, and perhaps even help get this article on track for a good article review. — Sasuke Sarutobi (talk) 10:30, 2 April 2018 (UTC)

Link to Ulrich Schmidt ?

In the section "Proof by computer" is Ulrich Schmidt linked as someone, who apparently thought he found a flaw in Appel's&Haken's proof. If you click on that link however you reach the article of a German serial killer and neither the English nor the German Wikipedia mention any mathematical activities. Either these are not written there, so that someone who knows these facts might write them there or there is a different Ulrich Schmidt meant. I however can't find anyone with that name, who is listed as a mathematician in the Wikipedia. Therefore I would suggest removing that link. --JT0202 (talk) 11:32, 19 August 2018 (UTC)

Possibly this Ulrich Schmidt? Anyway I agree with removing the link to the sex offender and have done so. —David Eppstein (talk) 11:40, 19 August 2018 (UTC)

Image in False disproofs

I can do it in three:

• right-most yellow to blue
• inner ring blue to yellow
• cyan to blue

Darcourse (talk) 11:43, 21 August 2018 (UTC)

This seems correct to me (where "cyan to blue" really means "inner cyan to blue"). Which would mean that the caption is false when it says that "it is necessary to change at least four of the ten regions to obtain a coloring with only four colors". I've reworded the caption, to remove that (unsourced) and apparently untrue claim. Paul August ☎ 14:53, 21 August 2018 (UTC)

I've had another look - the outside cyan makes the color count still five, so perhaps the original wording was right after all. Darcourse (talk) 02:54, 23 August 2018 (UTC)

Hmm ... yes you are right. So perhaps it is necessary to change at least four of the regions, but at least now the caption is certainly correct. Paul August ☎ 16:33, 8 September 2018 (UTC)

Why No Mention of G. Spencer-Brown's Many Proofs of 4CT?

Are "personality politics" involved here? — Preceding unsigned comment added by 1.129.106.149 (talk) 01:41, 8 September 2018 (UTC)

To avoid unnecessary embarrassment to Spencer-Brown? The sources we could use for this say things like "In December of 1976 G. Spencer-Brown, the maverick British mathematician, startled his colleagues by announcing he had a proof of the four-color theorem that did not require computer checking. Spencer-Brown's supreme confidence and his reputation as a mathematician brought him an invitation to give a seminar on his proof at Stanford University. At the end of three months the experts who attended the seminar agreed that the proof's logic was laced with holes, but Spencer-Brown returned to England still sure of its validity. The "proof" has not yet been published." [3] —David Eppstein (talk) 01:46, 8 September 2018 (UTC)

Mr Eppstein, so it seems that the answer to my second question above is an emphatic "Yes!".

Gardner's book (source of your above quote) also includes a slur on GSB from Conway. From other sources it is quite apparent that Conway was, and still is, jealous of GSB's success with LoF. Gardner sides with Conway, and many others, such as Knuth, in their contempt of GSB. All of which is an example of old-school Mathematics being reduced to "personality politics" at its most childish. And Mathematics used to be such a beautiful, non-political, place to visit.

Anyway, the above quote, from Gardner's book ~2007, states that "The [GSB] 'proof' has not yet been published.". As I am sure you are aware, Mr Eppstein, that is a false statement. Why repeat that falsehood here? Furthermore, did all "the experts who attended the seminar" in ~1977 publish a clear account of the "logical holes" in GSB's proof, perhaps in the form of an academic paper? If not, then the claims of "holes" are unsubstantiated opinion. If so, then it is worth noting that many holes were found in early versions of the Appel-Haken "proof", yet that proof received much positive publicity. Even Wiles' first claimed proof of FLT had a hole in it (which he eventually fixed) and it also received much publicity and kudos.

It is becoming increasingly clear to me that GSB and his work are given the cold-shoulder, at least in "professional" mathematical circles, for petty personality reasons. Which, sadly, means that the "Age of Reason" is well and truly dead. Is that what you want? — Preceding unsigned comment added by 1.129.108.113 (talk) 00:58, 9 September 2018 (UTC)

Searching MathSciNet for Spencer-Brown as author reveals that the only publication listed there is his Laws of Form (1972). So, clearly, his supposed proof has not been published in a reputable mathematics journal, because all such journals are listed in MathSciNet. If it has been published somewhere else, and some other collection of experts have vetted his proof and assert its correctness, perhaps you can tell me where these publications are to be found. Searching Google scholar did find uncolorable trivalent graphs but it appears to be a transcription of a lecture rather than a refereed journal paper and has not been cited by anyone else (at least, not by anyone else indexed in Google Scholar), so finding it did not lead me to the reliable secondary sources that we should be using as the basis for Wikipedia articles. And if you try to read that article you will quickly discover that it does not contain a proof by the standards of mathematics — it is full of vaguely-defined or undefined terms, incomplete case analysis, and unsubstantiated assertions that any counterexample must have some very specific form. —David Eppstein (talk) 01:06, 9 September 2018 (UTC)

Mr Eppstein,

Firstly, I note that Perelman was awarded a CMI Millenium prize (declined) for his proof of Poincare on the basis of three unrefereed papers deposited at arXiv.org (an UN-reliable source?), together with a short lecture tour of USA. The awarding of the CMI prize was no doubt aided by refereed papers written by other academics (including the Chinese group who wanted credit for the first "full" proof because they claimed to fix "holes" in P's work). But the relevant point here is that, despite Perelman's work NOT having the "refereed-stamp-of-approval", these many other academics were quite happy to read, discuss, and write about Perelman's work, thus publicising it. That is, in this case there was no prerequisite to be "published in a reputable mathematics journal" in order to get a reasoned dialogue started.

Secondly, if you put MathSciNet aside for a moment, and do a quick google of LoF, you will find that it has English editions from 1969, 1972, 1979, 1994, 1997, 1999, 2008, 2009, 2010, 2011, 2015, as well as German language (+?) versions. So not just "1972". I recently gave my 1979 copy (which is sans 4CT) to my youngest son who is doing some digital circuit design, because the LoF approach makes such work so much easier. So I updated to the 2015 LoF, which covers 4CT in Appendices 5 and 6, and has perhaps even more interesting stuff in Appendices 7, 8, 9. I guess the 4CT Appendices were first added ~1997, some 20+ years ago? While waiting for this latest copy of LoF to arrive, I found the "UTG" paper that you mentioned on the web, and also several papers on GSB's proof by your fellow countryman Louis H. Kauffman, in "Discrete Mathematics". Unfortunately, Kauffman's 2005 explanation (even after his 4+ years of revisions) is not as good as that in LoF itself. In fact, most every refereed paper I found on 4CT, and there are many, give very sloppy proofs "by the standard of mathematics". That is, nowadays "refereed" does not imply "high standard".

Anyway, aside from Kauffman and very few others, it seems no one wants to talk about GSB's work. Despite GSB's proofs (he has multiple different versions) being in the public domain for some 20+ years, I have not managed to find a single, objective, paper/website/whatever that clearly spells out any logical flaws in his work. That includes these talk pages. There is ~1 line on GSB back in Archive 3 (2006), with that addition to the article being later deleted for no given reason. Meanwhile, almost all of Archive 2 is discussion on "Dharwadker's proof"! (<- Yes, probably because D was doing much of that discussing!)

To sum up, if GSB's proofs of 4CT are flawed, then does anyone know where I can find a clear account of those flaws? — Preceding unsigned comment added by 1.129.105.78 (talk) 12:48, 10 September 2018 (UTC)

This page is not the correct place to discuss the merits of Spencer-Brown's claimed proof of 4CT, nor whether Spencer-Brown's claimed proof has been given short shrift by the mathematics community. The purpose of this page is to discuss possible changes or additions to its associated article. And any such changes or additions must be supported by reliable sources, see WP:VERIFY. Paul August ☎ 15:32, 10 September 2018 (UTC)

Mr August, two questions:

1. Is Elsevier's journal Discrete Mathematics a "reliable source"?

2. If a paper on 4CT was published in a "reputable mathematics journal" (to use Eppstein's phrase) some 13 years ago, and if the author of that paper wrote in the introduction "This work ... deserves careful consideration. ... these concepts are central to understanding the nature of the four color theorem...", and if there have been no critical responses to that paper since it was published, then should not that paper and the work therein be mentioned somewhere in this article about the Four Color Theorem? — Preceding unsigned comment added by 1.129.106.209 (talk) 12:31, 11 September 2018 (UTC)

1. Yes.

2. Perhaps. You can, if you like, propose some appropriate text with sources, here for discussion.

Paul August ☎ 14:30, 11 September 2018 (UTC)

This is Kauffmann's "Reformulating the map color theorem". Kauffman is careful to say that Spencer-Brown makes an assumption of a certain "principle of irreducibility" as "axiomatic" and that this principle is actually equivalent to the 4CT. I.e., if you assume an equivalent form of the 4CT as an axiom, you can prove the 4CT as a consequence of that axiom. But Kauffman provides a useful dictionary for translating Spencer-Brown's terminology into something more standard. I'm surprised we don't have a section on equivalent formulations of the theorem (e.g. in terms of 3-edge-colorings), and the formulation in terms of "formations" could definitely be mentioned in such a section. —David Eppstein (talk) 15:50, 11 September 2018 (UTC)

"Three colors are adequate for simpler maps"

In the section regarding "real-world" maps, it says

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

Surely it's actually very common for four colors to be required, such as when three countries/states are touching each other and the ocean. E.g. File:Map of Australia.png, or Central Europe. This seems even simpler than "one region is surrounded by an odd number of other regions that touch each other in a cycle," and common enough that the statement "three colors are adequate for simpler maps" seems quite out of place, since this kind of map is very simple and common indeed.

I'm going to remove the line, and the following line about 5-color-maps, since that was already mentioned earlier in the article, and, anyway, is proved a fortiori by the 4-color-theorem, so isn't actually relevant to the discussion on real-world maps. 50.255.135.49 (talk) 18:52, 14 September 2018 (UTC)

Hello, it's that dude formerly known as exxxz again. Somebody seems to agree with me

Somebody else has pointed out that any region with 3 or any higher odd number than 3 regions, surrounded by a ring of another colour, requires 4 colours, and that any region surrounded by 3 or any higher odd number of sectors also requires 4 colours. I pointed this out ages ago, along with some other fundamental 4 colour maps, for which I was completely rubbished. Have another look at my talk page post from ages ago, particularly the one in which I gave diagrams. I challenge anyone to post a map that I've not covered. Otherwise I'm right, aren't I Edmund Xathrusz (talk) 03:41, 13 December 2018 (UTC)

You're making a correct statement about something that's not in dispute, but I won't call it "right", since you're not even addressing the right question. It's well known that there are planar maps that require four colors; anybody can easily make one. The problem is to show that there are no maps that require more than four. I.e., "the set of maps that require five colors is empty".

This cannot be proved by the local analysis that you keep posting, because it's not true for some surfaces that are only locally planar. A projective plane requires six colors, and a torus requires seven. Joule36e5 (talk) 04:00, 13 December 2018 (UTC)

Reference consistency problem?

While reading the article, I noticed that while all of the references are in the references section, some of the inline harvard citations are done using traditional inline citation while some are done using the superscript method and the notes section used in most other Wikipedia articles. Examples of the notes method are found in paragraph 2 and 3 of the lead, while an example of regular Harvard citation (without superscript to notes section) is found prevalently in the Generalizations section.

I am wondering if this is allowed and considered consistent, or if we should make it more consistent, and if so which one should be adopted. From the last Good article nomination, it seems that referencing was the only major thing preventing it from becoming GA, and the article still seems well written except for this referencing issue. _{Integral Python} ^{click here to argue with me} 18:45, 8 March 2019 (UTC)

Contradiction in proof section?

The last paragraph in Four color theorem#Proof by computer: 'They responded that the rumors were due to a "misinterpretation of [Schmidt's] results" and obliged with a detailed article' - without further comment it looks like Schmidt was wrong. But then we learn that their book later " explained and corrected the error discovered by Schmidt [...]", so Schmidt was right? Related question: Why was it "a rumor" years after the master thesis was published? --mfb (talk) 07:22, 16 May 2019 (UTC)