Abstract:
The four color map theorem states that no more than four colors are needed to color the regions of any map so that no two adjacent regions have the same color. More specifically, the theorem states that no more than four colors are required to color the vertices of any planar graph where any two adjacent vertices don't have the same color. This paper shows how the theorem arises from a broken correlation between the number of colors and the number of vertices (dots), and, how repairing this broken correlation leads to maps requiring more than four colors. However, if three dimensions are not invoked on a on planer graph, it can be shown that no more than four colors are needed to color it.
Premise: All maps, regardless of their shapes and sizes, can be represented by planer dot-and-line diagrams. Such drawings make analysis easier and more universal. Each dot (vertex) represents a country and each line represents a border. The rules are any two dots connected by a line cannot be the same color and lines cannot intersect.
Suppose there is a single country. We can represent it with one dot and one color:
Take two randomly-positioned dots. Draw a line (border) between them. These two dots and the line can be mapped to a straight horizontal figure. This will allow us to make apples-to-apples comparisons between different random maps. Also note that we now have two dots and two colors.
Next we have three randomly-positioned dots mutually-connected by three lines. Here again we can map this to a horizontal figure. We make sure the lines do not intersect since they represent borders on a two-dimensional (2D) map. There is now three dots and three colors.
We repeat the previous process with four dots and four colors:
There appears to be a pattern: one dot requires one color; two dots require two colors: three mutually-connected dots require three colors--and four dots, mutually-connected, require at least four colors. If we connect five dots, will we need at least five colors? According to the diagrams below, we can't mutually connect all five dots without intersecting lines:
Since the purple dot and the blue dot are not connected, they can be the same color:
The pattern we observed earlier is broken. Five dots don't require a minimum of five colors as expected--they only require four. Perhaps six dots require at least five colors:
Nope! Maybe seven or eight dots require at least five colors:
Wrong again. But take note of a new pattern: when we add a new dot beyond four, and do our best to mutually connect all dots so their colors cannot be reused, at least two dots are not connected. As a result, they can be the same color, and, the total number of required colors never exceeds four no matter how many dots we have, no matter how big and complex the map. However, this is only true if a 2D map never invokes a third dimension (3D), i.e, there is only north, south, east, west, and no elevation or up and down. At the diagram below, we invoke 3D by allowing the orange line to cross over the black line. Try to imagine the orange line lifting off the page to cross over.
Now all five dots are mutally-connected. Five dots now require a minimum of five colors. In 3D, the ratio of colors (c) to dots (d) is always one. In 2D, this ratio breaks down when there's more than four dots:
Below is an example of eight dots, mutually-connected in 3D, requiring at least eight colors:
If 3D is invoked on a 2D plane, lines are allowed to cross. This potentially allows up to an infinite number of mutual connections between an infinite number of dots, and such a map requires up to an infinite number of colors.
If we examine other dimensions (D) of space, we make the following observations: if D = 0, there is always one dot and one color. If D = 1, there is only one type of map: a straight line. It is fairly obvious that only two colors are needed for this map, no matter how big it is.
When D = 2, and lines are not allowed to cross, it appears that no more than four mutual connections can be made between dots, and no more than four colors are ever needed no matter how big or complex the map. As mentioned earlier, a 3D map could require up to an infinite number of colors. Further, we should note that 0D only accommodates 0D maps (a single dot), 1D accommodates 0D and 1D maps, 2D accommodates 0D, 1D, 2D maps, and finally, our 3D space can accommodate all maps from 0D to 3D. Below is a graph that illustrates our findings:
Take a look at the 2D column. It indicates that 1-color, 2-color, 3-color, and 4-color maps are possible. But are four colors really the maximum needed for any possible 2D map that needs more than three colors? It would take a great deal of computing power to test an infinite number of different types of maps that can exist in 2D space. The data table below lists what we know and a question mark where there is uncertainty:
The data table suggests a pattern where we can predict that the question mark should equal four, i.e., no more than four colors are required to color any 2D map. But is there really a pattern or are the numbers listed coincidental? Can we show that the numbers are logically and mathematically connected? The answer is yes:
Dimensions zero through three each have a maximum number of colors necessary to color maps in their respective spaces. The pattern between them is a tan function (see equation 3). So we can logically conclude that no more than four colors are needed to color any 2D map? Yes, as long as 3D is not invoked on a 2D map. If 3D is invoked, here's what is possible:
Imagine an exoplanet approximately 50 light-years from earth. It orbits a yellow star within the Goldilocks zone. It has a vast ocean. In the middle of that ocean is an island continent with five countries: purple, red, yellow, green, and brown.
In the middle of the island is a mountain. The red and purple countries share a border at the mountain top. The green country created a tunnel through the mountain to connect with and share a border with the yellow country. Each country shares a common border with the remaining four. Not counting the ocean, at least five colors are needed to color this 2D map.
References:
1. Four Color Map Theorem. Wikipedia
2. Weisstein, EW. 2002. Four Color Theorem. Wolfram MathWorld
3. Najera, Jesus. 10/22/2019, The Four-Color Theorem. Cantor's Paradise
4. Planer Graph. javatpoint.com.
No comments:
Post a Comment