N-Color Theorem

I had been casually working on the 4-Color Map Theorem off and on since 1991 when I was studying computer science at USC. I thought I had made some progress when a few years later a rigorous computer proof was published. However, that proof required an exhaustive analysis by computer and was not easily understood by a human, so I continued, off and on, to look for a simple proof. I'm no longer sure a simple proof is available, but I give here what I have so far. It convinces me, but it would probably not hold up to rigorous mathematical inspection.

Lofting the problem to 3D is also interesting, and it turns out that those proofs (both the limited and general cases) are much simpler, counterintuitive as that notion may seem.

Two Dimensions

Cartographers have known for centuries that any map can be colored with four colors with no two bordering contries colored the same. Conventionally, a fifth color (say, blue) is reserved for water, but the principle of four colors remains. It was generally considered to be true, but no proof existed. There are also point borders, as at a four corners (which would conventionally require only two colors), and the proof is the same whether we consider point borders or not.

It was fundamental computer science that got me thinking about the four color map problem. It occurred to me that a data structure called a graph (nodes and connections) formed a "dual" with a map. That is, abstracting out unnecessary detail from a map left only the essential connections of a country with its neighbors, none of which could be colored the same as it.

So we start with fundamentals. A set of atomic symbols forms an alphabet. For convnience of exposition we could use letters, numbers, colors, geometric shapes, or whatever. The only feature of an atomic symbol is that it is distinguishible from other atomic symbols. Often it is convenient to use a two-symbol alphabet, called binary. These could be one and zero, a and b, etc. For the four color theorem, of course, we will use four symbol alphabet. We could denote color1, color2, and so on, or memonics such as r for red, b for blue, etc. It doesn't really matter. Remember that atomic symbols are featureless except for being distinguishible.

Now we proceed to an assembly of atomic symbols called a "string." We start with a symbol and then connect another symbol, and continue to make a linear assembly, a string, of any length. For our purposes, we can construct a string as long as we need by adding another symbol, so we don't need to talk about infinite length strings. Suppose we have a string of seven symbols of a four element alphabet. One particular symbol is the start of the string, the beginning, and the last symbol is the end. If we were to encounter this string floating in mental space, we wouldn't know which end was the start end, so we need a special tag to denote the start of the string.

So how many symbols (colors), at most, would it take to ensure that a string would have no two adjacent symbols the same? I think it's evident by inspection that two will suffice, e.g., red, green, red, green, red, green, etc.

Next I introduce a concept I didn't find in computer science text books. We bend the string around and attach the end to the beginning symbol forming a structure I call a "ring." Now it has no beginning so if you find a ring floating in mental space, you don't need a special tag to find out where the beginning is because it has none. N-element rings are therefore actually simpler than N-element strings. This is not important to the theorem, but interesting to note.

How many colors at most for a ring? If it's a ring with an even number of elements, only two, but the general case takes three colors. We can now extend our constructions of strings and rings into a general 2D graph. Note that graphs in 3d can be easily smashed into 2D as crossed connections are allowed. Because the 4-color theorem is in a 2D map world, its corresponding graph is in 2D, and you may note that there are no crossing node connections in the map dual graph.

Now take a particular country in our map transformed into a graph. We color our country arbitrarily a particular color, say color one. The countries bordering that country form a ring around it, which we know takes three colors maximum, colors two, three, and four.

So for any particular country we can show four colors maximum required, and extending that through a whole generalized map is not an issue. Here is the "proof by induction" part: We know that taking one of the ring countries and its neighbor (the first country, color one) allows construction of a bordering ring with three other colors that include color one.

Incidentally, this "proof" applies to maps on any smooth surface, whether an infinite plane, a sphere, a torus, etc.

Three Dimensions

While doing engineering at TRW (later bought by Northrop Grumman) I learned to use a number of 3D CAD systems that used constructive solid geometry (CSG), invented, by the way, by my PhD dissertation committee member Prof. Ari Requicha. These systems model mechanical parts and assemblies as 3D solids. The user can set colors for the parts of an assembly such that (by convention) no two adjacent parts are the same color. One of the systems in use at the time (CATIA) allowed up to 64 different colors for parts. Newer systems might have a much larger number of colors to choose from. In actual use, however, most designers used only a handful of colors, say six or seven, tops.

But it's an interesting question, how many colors would you need to color any 3D assembly such that no two adjoining parts had the same color?

Theres a simple case and a general case. In the simple case we do not allow parts to penetrate one another. That is, no holes allowed. Each part is, technically speaking, homeomorphic to a sphere. Of course, a CAD system that does not allow penetrations is impractical to the point of being useless, but it allows us to set a finite number to the colors required: eight. The proof is contained in this short story, Colors Problems (PDF).

The more practical case of penetrations allowed requires an infinite number of colors, and the proof is by construction. Here it is:

Take a cylindrical part and color it 1. Now pierce (penetrate) it with a cylinder half its diameter such that the cylinder axes intersect, and assign it color 2. Now penetrate that assembly through both cylinders (such that all axes intersect at a point (and colinear to none)) with a color 3 cylinder half the size of cylinder of color 2. Repeat with colors n + 1 ad infinitum.

Email Richard dot J dot Wagner at gmail dot com