# Four Color Theorems: Graphs vs. Maps [closed]

This question has changed dramatically from its original form. Please See the improved question.

ORIGINAL QUESTION:

There are two variants of the four color theorem that are commonly cited:

(4CTG): Every planar graph is 4-colorable.

(4CTM): given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color (copied from Wikipedia).

TWO PART QUESTION:

1. I think that if we use the mathematical definitions that most closely capture what we mean by separation, contiguous, and adjacent then 4CTM (popularized version) is false. I will state definitions that I think best capture these terms along with what I think is a counterexample.

2. (Assuming the "counterexample" holds...) My definitions are purely topological and I suspect that the theorem may require a geometric element to be true. If you can offer stronger or different conditions that make the (popularized) theorem true can you comment on the necessity of the new conditions and whether the theorem is inherently geometric? What is it about my definitions that makes them too weak? Also, do the new conditions truly reflect the 4CTM (popularized version) conditions or is (the popularized) version missing something crucial?

Definitions:

Definition: Separation of $\mathbb{R}^2$: A separation should be a set of sets that cover $\mathbb{R}^2$, but this leads to ambiguity about borders between two regions. To avoid this ambiguity it seems reasonable to opt for a topological partition in which borders don't belong to regions. Thus, define a separation to be a set of open sets, $\{U_1,\ldots,U_n\}$ such that the union of their closures is $\mathbb{R}^2$.

Definition: Contiguous should mean connected, and since this is $\mathbb{R}^2$ connected open sets are path-connected, so we could equivalently require path-connected.

Definition: It is clear that the theorem is false if we allow adjacencies to include corners, i.e. that boundaries overlap at points. For me, and I think most people, adjacent means that the boundary shared by two regions contains a curve (of positive length). Thus, define two countries to be adjacent if there exists a homeomorphism of $[0,1]$ into the intersection of the boundaries of the regions.

Counterexample (to the version I have just defined):

For any $n\ge5$ we can construct $n$ path-connected regions that are pair-wise adjacent. A coloring would require $n$ colors. I will construct the regions to lie in a finite area to rule out infinite area as a possible reason for the counterexample. The remaining portion of $\mathbb{R}^2$ could be considered an $n+1$th region or one could replace $\mathbb{R}^2$ by $D$ in the definitions, where $D$ is the closure of the union of the regions.

Define $y_j = \sin(1/x)+j/n$ for $x\in(0,1)$ and $j=0,\ldots,n$.

for $k=1,\ldots,n$ let $U_k = \{(x,y): x\in(0,1), y_{k-1}<y<y_k\}$.

It is clear by definition that $U_k$ is open and path-connected. I also claim that the boundary of $U_k$ contains $\{0\}\times[-1+(k-1)/n,1+k/n]$. Consider first $U_1$ and the point $(0,1)$. Since $\mathbb{R}^2$ is a metric space it suffices to show that a sequence in $U_1$ approaches $(0,1)$. Let $\tilde{x}_m=\frac{1}{3\pi/2+2\pi m}$ for $m\in\mathbb{N}$ and $\tilde{y}_m=-1+1/(m+n)$. Then $y_0<\tilde{y}_m<y_1$ and $(\tilde{x}_m,\tilde{y}_m)\to (0,1)$. A similar sequence can be constructed for any $(x,y)\in\{0\}\times[-1,1+1/n]$, so that $[-1,1+1/n]\subset\delta U_1$.

Since $U_k=U_1+(k-1)/n$, the boundary of $U_k$ is $\delta U_1$ shifted up by $(k-1)/n$ for $k=2,\ldots,n$. Thus, $\{0\}\times[-1/n,1+1/n]\subset\cap_{k=1}^n \delta U_k$ and is clearly homeomorphic to $[0,1]$ so that each of the $n$ regions are adjacent.

Note that if it seems weird that the shared boudary is on the left (west) hand side of each country, we could easily create $n$ new regions by reflecting across the $y$-axis.

This question is inspired by this article: Hud Hudson (May 2003). "Four Colors Do Not Suffice". The American Mathematical Monthly 110 (5): 417–423. JSTOR 3647828. It is linked from the Wikipedia page on the four color theorem.

This construction and Hud Hudson's construction result in boundaries of infinite "length". Unfortunately, length seems a geometric concept, whereas the theorem has a very topological flavor. Furthermore, a restriction on length would exclude a large class of cases in which the statement should hold, such as when the some of the boundary lines are merely parallel horizontal lines in the plane. If you feel that length is the root of the problem can you comment on whether the theorem is not truly topological and why partitions that are well behaved except for boundedness need to be treated separately.

• It seems to me that a (finite) planar graph is a (finite) graph embedded in $\mathbb R^2$. The regions are the connected components of the complement of the embedded graph. Mar 7, 2015 at 16:04
• Can you say more about the "complement" of the graph? Mar 7, 2015 at 16:08
• Since the graph is embedded as a subset of $\mathbb R^2$, therefore the complement is just the set-theoretic complement. For example, if the graph is $S^1$ embedded in $\mathbb R^2$, then the complement is of two connected components (Jordan curve theorem). Mar 7, 2015 at 16:14
• In fact, it's just a matter of duality, therefore the conditions of duality theorems should be satisfied. For more details, see Alexander duality, or Poincaré duality, etc. I'm not familiar with these stuff. Mar 7, 2015 at 16:41
• The issue is that you don't get to use the definition you think describes best those concepts. You must use the formal definition introduced before the Theorem is proven... Mar 7, 2015 at 16:53

This statement of (4CTM) is not right. You quoted from wiki, but if you read a little down this is what they say.

"The intuitive statement of the four color theorem, i.e. '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', needs to be interpreted appropriately to be correct."

You should quote "intuitive statements" in mathematics as theorems, especially from Wiki. Always quote the precise statement. And in this case even wiki warns you that this is the case.

The definition you use for separation is, if I am not mistaken, not the one which is usually used. When we define a map we assume that each region has a boundary which is a simple, closed, piecewise smooth curve.

Because of this, we only need to require connected, because I think this automatically implies path connected (so we don't worry about these two issues).

When I am teaching graph theory, this is the formal definition I use for maps, which is the definition from [1]:

By a map we mean (the faces of a) 3-connected planar drawing of a planar graph.

[1] R. J. Wilson, "Introduction in graph theory".

"I understand that this is not a formal statement. Wikipedia makes the disclaimer that these statements need to be interpreted correctly and this question is an attempt to explore possible interpretations. "

What do you mean by this? Theorems in mathematics are not open to possible interpretations. Theorems in mathematics have precise statements.

Wikipedia states the intuitive statement, and again you are stucked on it instead of reading the Theorem.

The (4CTM) is always stated the following day:

Definition By a map we understand bla bla bla.

Theorem Any planar map is $4$-colorable.

There is no place for interpretation, the Theorem is true with the above definition. As it stands, the wikipedia statement is an attempt to explain a very precise mathematical statement in layman terms, and usually these end up being complete junk..

If you change the definition of map you get a different statement. This statement might be a theorem or might be wrong. But it is a completely different statement.

I would advise you, when you search for mathematical theorems to ignore wikipedia, and look for the Theorems in the books. Any theorem in a book/research paper which uses a definition, like for example "map", has to give the precise definition of this concept someplace before, or a reference to the definition. And the theorem is true ONLY with that definition (no interpretation).

The wiki definition of a map is-because whoever wrote it tried to write it did his/her/its best to use layman terms only- from a mathematical point of view complete junk.

Added Again: the (4CTM) statement depends on the definition of maps. In graph theory, we typically study maps with polygonal faces. And it is not because we want to reduce the problem to (4CTG), it is exactly the opposite: historically I think people were interested to (4CTM) where (4CTM) was about real maps (here is where the "maps drawn by hand" comment comes from), and they realized that this reduces by duality to (4CTG).

Fary's Theorem allows us to extend the (4CTM) from polygonal maps to maps with closed curves as boundary, but this is a consequence of the one for polygonal faced maps.

If you drop these conditions, it is well known that the (4CTM) is not true anymore, if the faces have very odd boundary. But again that is a completely different result.

The discussion is really going in circles around the following: you think your definition of a map is the right one, and that the usual one is wrong. And that your "right" definition makes the (4CTM) wrong.

NOPE. Your definition of map defines a completely different notion of map. Lets call this a "topological map". And yes the (4CT-TM) is not true, but this doesn't contradict the (4CTM). And this is a well known fact.

Other than that, this post is just "my definition is better than yours", which is not an argument in mathematics. "my definition is better than yours" usually also means "my definition is different than yours", so you are studying completely different objects and theorems.

• If I'm understanding the definition, the boundaries in the counterexample are simple (do not intersect themselves), closed (by considering any sequence of points on the boundary) and piecewise smooth (The "top" and "bottom" are smooth curves and the left and right are just line segments). The boundary fails to be a 1-manifold at the top left and bottom left. These conditions don't seem to have anything to do with separation, so I would call them different conditions. Mar 7, 2015 at 17:47
• @cantorhead Closed piecewise smooth means defined on a closed interval, continuous on the close interval, and differentiable at all but finitely many points. Defining $\sin(\frac{1}{x})$ or some expression involving it on $(0,1)$ is not in general piecewise smooth, as it fails to have a continuous extension on $[0,1]$.... Mar 7, 2015 at 17:50
• The issue seems to be that my definitions focused on the regions. This definition focuses on the boundaries. My understanding is that a planar graph is a set of conditions on points (vertices) and arcs (edges). Let me think a little more before I accept your answer. Mar 7, 2015 at 17:50
• The book I was using forces arcs to be "polygonal". I only found a garbled version of your (Wilson) book, but it seemed to suggest that an edge (in the plane) could be any curve as long as it didn't intersect itself and had vertices as endpoints. Can you expand on that? Mar 7, 2015 at 17:52
• @cantorhead There is a theorem of Fary which is states that any planar graph which can be drawn with closed curves as edges, can be redrawn with straight lines as edges. I think you are right, smothness is not that important, BUT your curves need to be closed, that is defined on closed intervals. Fary Theorem says that all planar graphs can be redrawn with the boundaries being polygonal, that's why most books make this extra assumption. Mar 7, 2015 at 18:00

(sorry, this is more of a comment, but my rep is too low to post it like that)

I am rather green in topology and in graph theory I'm limited to my undergraduate training, but it seems to me that the heart of the matter is that you're unhappy about the 4CTM problem definition. I don't have a particular opinion on the subject, but changing its formal definition just constructs another new problem. This may be intimately related, but I think you can't really use it as a counter example to the 4CTM problem as its formally defined.

I have to admit I'm out of my depth here, but in particular I wonder whether when you specify $n$ path-connected regions with $n \ge 5$, aren't you effectively specifying a non-planar graph having $k_5$ as a minor under your definition of separation?

• Yes, that is exactly right. I'm constructing "map" in the plane that induces a non-planar graph. So the 4CTM problem that I have stated in topological terms cannot be turned into a 4CTG problem. Mar 7, 2015 at 16:12
• Glad to hear I managed to understand that properly at least :) But that's basically my very un-mathy point too really, to my mind 4CTM is defined as being mappable to 4CTG. When you specify a 4CTM-like problem that isn't, it's another problem. Mar 7, 2015 at 16:16
• I have edited the question to reflect that there is a 4CTM which is defined in terms of 4CTG. Mar 8, 2015 at 2:16
• I have also edited to make clear that I am not trying to create a counterexample to the formal graph theoretical version. Mar 8, 2015 at 14:29