Contents

Talk:Four color theorem

This is the talk page for discussing improvements to the Four color theorem article. This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic. New to Wikipedia? Welcome! Learn to edit; get help. Assume good faith Be polite and avoid personal attacks Be welcoming to newcomers Seek dispute resolution if needed Article policies Neutral point of view No original research Verifiability

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Archives: 1, 2, 3, 4, 5Auto-archiving period: 90 days

	Four color theorem was a Mathematics good articles nominee, but did not meet the good article criteria at the time. There may be suggestions below for improving the article. Once these issues have been addressed, the article can be renominated. Editors may also seek a reassessment of the decision if they believe there was a mistake.
Article milestones Date Process Result April 7, 2009 Peer review Reviewed October 29, 2009 Good article nominee Not listed
Current status: Former good article nominee

This article is written in American English, which has its own spelling conventions (color, defense, traveled) and some terms that are used in it may be different or absent from other varieties of English. According to the relevant style guide, this should not be changed without broad consensus.

This  level-5 vital article is rated B-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics High‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles High This article has been rated as High-priority on the project's priority scale. This was a selected article on the Mathematics Portal. Maps Top‑importance This article is within the scope of WikiProject Maps, a collaborative effort to improve the coverage of Maps and Cartography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MapsWikipedia:WikiProject MapsTemplate:WikiProject MapsMaps articles Top This article has been rated as Top-importance on the project's importance scale. Geography High‑importance This article is within the scope of WikiProject Geography, a collaborative effort to improve the coverage of geography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.GeographyWikipedia:WikiProject GeographyTemplate:WikiProject Geographygeography articles High This article has been rated as High-importance on the project's importance scale. WikiProject Geography To-do list: Here are some tasks awaiting attention: Article requests : See Requested articles/Social sciences/Geography, cities, regions and named places and Missing articles about Locations Assess : Tag related article talk pages with {{WikiProject Geography}}. To help assess the quality and importance of geography articles, please see: Unassessed geography articles and Unknown-importance geography articles. Cleanup : See Geography articles needing attention Deletion sorting : Listed at Geographic related deletion discussions Geographical coordinates : See Articles missing geocoordinate data by country Infobox : See Geography articles needing infoboxes Map : See Wikipedia requested maps Notability : See Geography articles with topics of unclear notability Photo : See Wikipedia requested photographs of places Stubs : See Geography stubs

I agree with David Eppstein that adding an entire section as a gallery to simply present different countries with their colorings is a bit overkill (especially with the map of America's at the beginning). I was thinking, though, of re-adding at least one of them to the section "Use outside of mathematics," since it seems apt. I was originally just going to place the Germany one in, but maybe adding a picture of a real-life exclave forcing 5-colors would be nice. In any case, I don't think it hurts to add a second picture illustrating how it works, since non-math inclined people are probably going to be interested in (more than one) examples of these type. I didn't want to just make the edit immediately though since the similar one had just been reverted. What do other people think? _{Integral Python} ^{click here to argue with me} 21:58, 24 May 2023 (UTC)[reply]

The article says "Forcing two separate regions to have the same color can be modelled by adding a 'handle' joining them outside the plane. Such construction makes the problem equivalent to coloring a map on a torus (a surface of genus 1), which requires up to 7 colors for an arbitrary map." That seems to imply that there's a planar map with just one noncontiguous region that requires 7 colors. But you can 4-color the contiguous countries and then use 1 more color for the noncontiguous one, so you only need 5 colors. I don't know how this should be rewritten. Nylimb (talk) 14:41, 23 August 2023 (UTC)[reply]

I don't follow "4-color the contiguous countries and then use 1 more color for the noncontiguous one". The problem in this section is that both regions marked "A" are constrained to have the same color. Under that constraint, there should be a map which requires 7 colors (although we don't draw it using the "handle" style of visualization). There's probably a clearer way to say all this, for example expanding on the example in the section in "Generalizations" describing the torus coloring problem, but I'm not sure quite what this would look like and whether it would be an improvement. Kingdon (talk) 10:40, 14 July 2024 (UTC)[reply]

"Forcing two separate regions to have the same color can be modelled by adding a 'handle' joining them outside the plane" -- true.

"Such construction makes the problem equivalent to coloring a map on a torus" -- false, because a torus map can require seven colors, while five colors suffice for a planar map with a single two-region country.

Proof: Consider the map obtained by removing both of the "A" regions. That map is planar, so it can be four-colored. Apply that four-coloring to the original map, and use a fifth color for "A".

Should we just delete that paragraph? Joule36e5 (talk) 21:20, 14 July 2024 (UTC)[reply]

Another falsehood: "A similar construction also applies if a single color is used for multiple disjoint areas, as for bodies of water on real maps ... In such cases more colors might be required with a growing genus of a resulting surface.", because all the bodies of water can be given a single color, regardless of how much the genus would grow by adding handles connecting them all. Anyway, I would be fine with deleting from "Forcing two separate regions" to "(See the section Generalizations below.)". —David Eppstein (talk) 06:26, 15 July 2024 (UTC)[reply]

In the section on three-coloring, it is stated that "A cubic map can be colored with only three colors if and only if each interior region has an even number of neighboring regions." but I can't find any easily available explanation of what a cubic map is. Maybe this should be explained, rather than requiring people to pass a paywall to read the cited article before they can understand what that sentence means? MasterHigure (talk) 11:33, 4 January 2024 (UTC)[reply]

I've added a wikilink. Joule36e5 (talk) 00:23, 20 February 2024 (UTC)[reply]

Isn't this section just plain misleading? It states that "A cubic map can be colored with only three colors if and only if each interior region has an even number of neighboring regions." But then it gives the US map as an example of an application of this statement when the US map is in fact not cubic! Moreover, since planar graph 3-colorability is NP-complete, it cannot be that the simple cubic map criterion used for testing if three colors suffice can be applied in general to all planar maps (that are not cubic). --Litmus58 (talk) 18:40, 14 March 2024 (UTC)[reply]

Maybe a sentence added to the lead, to the effect of "It is impossible to draw five bodies that are all touching each other, which would be required for the theorem to be disproven", would help more practically-minded people to grasp it intuitively. :) --Kraligor (talk) 16:07, 19 February 2024 (UTC)[reply]

That would be incorrect. It is a very standard misunderstanding of the theorem. The actual theorem is not about the impossibility of five regions touching each other (for which see Kuratowski's theorem). Minimal graphs that require five colors do not have to have five vertices, just as minimal graphs that require three colors can be cycles of any odd length, not just triangles. —David Eppstein (talk) 18:15, 19 February 2024 (UTC)[reply]