Four-Color Theorem Analysis — Rules To Limit the Problem

2013.07.10   prev     next

THE four-color problem was solved in 1976, then later the solution was simplified somewhat. But even the simplified solution is extremely complex and computer-assisted. Since there is no proof that a simpler solution does not exist, I took it upon myself to look for one. Unsurprisingly I did not succeed, but I found a few rules to limit the problem, which may be worth sharing. (Perhaps I am not the first to discover any of these; I have not researched what has been discovered about the problem in general.)

Rule #1: Three-Way Nodes Only

If point P is on the border between countries, then border will lead off of P in at least two directions (otherwise the map is defective). If border leads off of P in exactly two directions, then P is an uninteresting, arbitrary point on the border between two countries. But if border leads off of P in at least three directions, then we will call P a “node.”

Suppose border leads off of P in more than three directions. Then, suppose we put an arbitrarily small, circular country C over P, such that all the countries that met at P are now adjacent to this new country C. Otherwise, the map is unchanged. All the countries that existed before the change still exist, and they are all adjacent to each other in the same ways that they were before. So the addition of C makes the coloration of the map only harder, not easier in any way.

The addition of C also replaces the more-than-three-way node P with a set of three-way nodes (around country C).

Therefore, we can require that any map use only three-way nodes, and the four-color problem has not been compromised; i.e. if we can find a solution to the four-color problem with this three-way-only restriction in place, then we have solved the four-color problem, period.

Rule #2: One-, Two-, and Three-Country Donuts Disallowed

Suppose country A is a “donut,” i.e. it has at least one “hole” in it that may contain a sub-map of unlimited complexity, In that case, if we discover a technique T that is guaranteed to color the set of countries hole-plus-A, that same technique T can also be used to color the set of countries exterior-plus-A. Then, simple color substitution can be used to make the two solutions use the same color for A, creating a unified solution for the entire map.

Therefore, donut countries can be prohibited, and the four-color problem is not compromised; i.e. if we can find the solution (T) without the interior (“hole”) section in-place, then we also can solve the full map that includes the “hole” section.

This same logic can be extended to a ring (donut) of two or three countries because, since every country in the donut touches every other country in the donut, the donut countries must use distinct colors from each other, and so the color-substitution plan described above can be employed. So we can also ban two- and three-country donuts. But beyond three-country donuts, there are multiple, different ways to color the countries that make up the donut, with no obvious guarantee that the color substitution plan will be workable.

Rule #3: Every Country Must Be Adjacent To At Least Four Other Countries

Suppose you have a map that needs to be colored, and you take this approach: First, find any country that is adjacent to no more than three other countries. Number that country 1. Now, find any unnumbered country that is adjacent to no more than three other unnumbered countries. Number that country 2. Continue this process, finding unnumbered countries that are adjacent to no more than three other unnumbered countries, and numbering those countries incrementally. (Note that each time you number a country, you potentially are creating new countries to number, since only the number of unnumbered adjacent countries counts towards the required total of three-or-less.)

If you successfully number the entire map, then it is now trivially easy to color it: Simply color the countries in reverse numerical order, using any available color. Each time you color a country, it will be adjacent to no more than three other colors, so there will always be a color for you to use.

Suppose, however, that you number as many countries as can be numbered, but there are still unnumbered countries remaining? In that case, the remaining countries are grouped into one or more contiguous blobs. The problem is now simply how to color each of these blobs — after that, the numbered countries can be colored in reverse numerical order as described a­bove.

For the sake of the argument, we can assume that there is only one of these blobs, because they are isolated from each other: If we can figure out how to color one of them, we can color all of them.

This blob can now be considered a map. And in this map, every country is adjacent to at least four other countries (because otherwise we would not have exhausted the above-described numbering ac­tiv­i­ty).

So, in approaching the four-color problem, we can require that every country be adjacent to at least four other countries, and the four-color problem is not compromised.

Side Note About Consistency

If you replace a more-than-three-way node P with a small country C (as described in Rule #1), then C will be surrounded by a donut of countries, and that donut will — as required by Rule #2 — consist of more than three countries. Also, country C will be — as required by Rule #3 — adjacent to at least four other countries.

(Note: What if P was a four-way node, but was not actually the meeting point of four countries, because one of the countries wraps around and meets P from two different directions? In that case Rule #2 is already being violated.)

Euler’s Formula

Euler’s formula says that

    nodes - edges + countries  =  2

(where the infinite outer space counts as a country).

In that notation, Rule #1 can be expressed as:

    2 * edges / nodes  =  3

(The 2 is there because each edge is shared by two nodes, and so must count twice to give us the number of edges coming off of each node.)

And Rule #3 can be expressed as:

    2 * edges / countries  ≥  4

(Again, the 2 is there because each edge is shared by two countries, and so must count twice to give us the number of edges bordering each country.)

Now we have three formulas and three variables. Solve (exploiting the fact that the variables are known to have positive values) and you get:

    countries  ≥  6

    nodes  ≥  8

    edges  ≥  12

That doesn’t seem especially helpful.

I tried thinking about the complementary graph, in which each country is changed to a node, and each node is changed to a country — but that didn’t seem to accomplish anything. It’s just equivocating with the terminology, which in no way alters the logic or the results.

Rule #4: Must Build the Map One-Country-At-A-Time By Adding Countries In the Outside Space

This rule says that you must start with a single country (nominally a circle). Your second country must bud off of the first country. Then every country you add after that must be formed by T-ing off of a pre-existing edge into the outside (infinite) space, then T-ing back into a pre-existing edge.

Note A: T-ing off of, or into, an existing edge creates a three-way node, as required by Rule #1.

Note B: You may not stop building your map except when it is in a state that satisfies Rule #3.

Note C: When adding a new country, you may not wall-in an existing country X such that X no longer accesses the outside space if doing so would cause X to be adjacent to less than four other countries — otherwise Note B will be impossible.

Rule #4 does not compromise the four-color problem because any map (that satisfies Rules 1-3) can be constructed with the Rule #4 restriction in place: Any contiguous map can be built one-country-at-a-time, from the inside out.

Out of Ideas

To be continued...?

prev     next