Talk:Four color theorem

Equivalence to torus coloring is wrong

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)

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)

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

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)

@Joule36e5: Here: "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. you're clearly wrong. A number of colors some specific map requires is irrelevent. You might say on every surface there exist a map requiring exactly two colors, but that doesn't prove equivalence of those surfaces.

Topologically, a plane with two holes glued with a handle is exactly a torus with a pinhole (one point removed) so each map possible on one can be also created on the other one. As a result, five colors do not always suffice. The fact they suffice for this specific map is an example that '4 isn't always enough', which is something completely different from '5 is always enough' and does not imply that. --CiaPan (talk) 13:47, 19 July 2025 (UTC)

I don't think I was referring to any specific map, but let's try again. My assertion is that (1) a planar map, with the additional constraint that at most one country has a single exclave, can always be 5-colored. (Proof: 4-color the map with that country removed.) I agree that (2) any "planar with one exclave" map can be drawn on a torus (proof: attach the exclave with a handle), but (3) there exist toroidal maps which cannot be reduced to a planar map with a single exclave (proof: any toroidal map requiring more than 5 colors). Since the reduction only works in one direction, the two are not equivalent. Joule36e5 (talk) 19:01, 19 July 2025 (UTC)

Cubic map

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)

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

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)

Alternative non-mathematical explanation

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)

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)

Summary of proof ideas has wrong and dubious statements

The section, as it stands, has dubious statements and some verifiably wrong ones.

Wrong:

- The formulas with $iv_{i}$ (e.g. $\sum _{i=1}^{D}(6-i)v_{i}=12$) seem completely false. I don't really see how indexing and degrees would combine... (the sum obviously varies on the way you index nodes). Even for a simple triangle graph, this equation does not hold. I don't really know what was originally meant there, but this is flawed. The conclusion "that there is at least one vertex of degree 5 or less" doesn't come from this, even if it were true.

Dubious:

- "If this triangulated graph is colorable using four colors or fewer, so is the original graph since the same coloring is valid if edges are removed". Well, how exactly? If you remove triangulation edges, e.g. in a face that was a pentagon before, the triangulation will yield three triangle faces, colored by either two or three colors (not one), which color do you choose when removing the triangulation edges? Simple examples hint that this statement may be hard to prove, and not just "same coloring is valid" (one has to double-check the original source). Also, as a side note, "triangulated graph" jumps to the planar graphs page, incorrectly.

I did not read past these statements; possibly there may appear similar mistakes in other paragraphs too. Misinnyo (talk) 19:42, 4 October 2025 (UTC)

Re "Even for a simple triangle graph, this equation does not hold": for the triangle graph, $v_{2}=3$ and all other $v_{i}$ are zero. So when you sum, the only nonzero term is $i=2$ for which $(6-i)=4$, $v_{i}=3$, and the sum is 12. The equation holds. —David Eppstein (talk) 20:01, 4 October 2025 (UTC)

The triangulated graph is using vertices, not polygons, as the objects to be colored. (I.e., it's the dual graph to what you're thinking of.) So removing an edge is removing a coloring restriction.

To rephrase it in terms of polygon coloring, if you originally had a vertex with five polygons meeting at a point, the "triangulation" would be to create two new points there and then separate them so that some of the polygons previously intersecting at a point now share a small edge, and all of the corners are now shared by only three polygons. If that map can be colored (despite the new restrictions caused by now-adjacent polygons), then so can the original. Joule36e5 (talk) 22:29, 4 October 2025 (UTC)