Four Color Theorem Applied to 3D Objects
| Four Color Theorem |
|---|
 |
Four Color Theorem
- This picture shows an example of the extension of the four color theorem to non-flat surfaces using a bumpy 3D shape.
Contents
Basic Description
The Four Color Theorem states that any planar map needs at most four colors to be colored so that no bordering regions are the same color. So when coloring a flat map with four colors, same color regions only ever need to touch at their vertices. They will never need to share an edge. To clear things up, vertices are points on a graph. Edges are the sides of a region. A map is a collection of points. And Graph Theory is the study of graphs. Also, a planar graph is a graph in which no edges overlap each other.
The Four Color Theorem only applies explicitly to maps on flat, 2D surfaces, but as I'll be talking about, the theorem holds for the surfaces of many 3D shapes as well.
In the picture, a 3D surface is shown colored with only four colors: red, white, blue, and green. This picture is demonstrating the Four Color Theorem because not one object is touching another object of the same color. There are, however, two blocks that are not colored in. But we could easily complete the four-coloring of this map by coloring the upper block green and the lower block blue, demonstrating the Four Color Theorem.
A More Mathematical Explanation
- Note: understanding of this explanation requires: *Graph Theory
In order to figure which 3D surfaces the Four Color Theorem applies to, I started with a trial and error experiment.
How I Conducted My Research
I conducted my experiment of applying the Four Color Theorem to 3D objects by drawing nets of seven different 3D objects. Then I colored the nets as if they were just flat, 2D shapes. Then I did the same thing, but I colored the nets as if they were the actual 3D objects, keeping in mind that each face touches many other faces. In both cases I made sure not to color any two regions touching by edges the same color. Then I put my work into the chart and graph above.
The picture of the nets shows the minimum number of colors used to cover each shape. The first one in each set is a coloring of the 2D shape, and the second coloring in each set is done as if on the actual 3D object.
The chart above was the beginning of my research. The chart shows the difference between the minimum number of colors used to cover the 2D net of a 3D object, as well as the minimum number of colors used to cover the actual 3D object without any colors touching each other, unless by vertices (which is acceptable in the Four Color Theorem).
Observations
After doing my experiment, I noticed a lot of different things within my work. I also connected my results to graph theory, cycle graphs, and topology. This will show up later. What I noticed is as follows:
- All the shapes without a curved side have a higher minimum number of colors used to cover the 3D object than the 2D surface.
- The cylinder is the only object that has the same minimum number of colors used to cover the 3D object as well as the 2D surface (the net of the 3D object).
- I think the cylinder uses the same minimum number of colors to cover the 3D and 2D object/ surface because the curvature of the cylinder mimics how a 3D objects' faces touch multiple other sides.
- The two circular parts of the cylinder are also completely opposite each other in the 3D format, and as I noticed in the other 3D objects, opposite sides can always be colored the same color. However, there are not always multiple pairs of opposite sides.
- All the 2D nets are colored in at most 2 colors.
Connection to Graph Theory
Now lets get into graph theory. It was basically explained earlier, but I will get into Bipartite graphs which are the basis of my results applying the Four Color Theorem to 3D objects.
A Bipartite graph is a set of points that can be separated into two independent sets. The vertices within each set are not connected by edges. Only between the two sets are vertices connected.
As you can see, no points in the U set are connected by edges, which is the same for the V set. Edges do connect the two sets together, however. And if you were to spread the points out randomly but kept the same connections between the vertices, you would notice how the blue points can share edges with the green ones but not each other. For vertices of the same color to be connected, edges would have to cross, which would mean the graph could not be planar as is the overhead graph used in this project.
For a graph to be Bipartite it
- Has an even cycle (A set of points that create a shape like a square or a hexagon that have an even number of vertices).
- Is colored in two or less colors
- (Look into Graph Theory for other, more complex reasons for a graph to be called Bipartite)
This leads me into a discovery I made on my own before looking into Bipartite graphs. It was that if the base number of any shape is odd, more colors are needed to cover the 3D object than if the base number were even. A base number is the number of vertices in the base of the object. For example, in the pentagon to the right the base number is five. There are less colors needed when the base number is even because every other vertex can be colored the same color, which means that only 2 two colors need be used. If you have a shape like a square with an even base number, the colors of the vertices in the cycle graph would go: red, yellow, red, yellow (two colors). If you have a shape like a pentagon with an odd base number, the coloring would have to go: red, yellow, red, yellow, green (three colors). A cycle graph, by the way, is a a set of vertices with only one closed chain connecting the points (much like what a 2D shape looks like on paper).
Connection to topology
Topology is the study of properties of objects that survive when the objects are distorted. This type of property is very useful in figuring out the minimum number of colors needed for maps on non-flat surfaces, like the surfaces of 3D objects. If the key properties of a flat map for which the four color theorem applies survive when the map is distorted to cover the surface of a 3-D object, then we can still apply the four color theorem.
The four color theorem tells us that no more than four colors are needed to color a map on a flat, 2D surface so that no two bordering regions are the same color. So the property that matters here is adjacency, or whether two regions border each other.
Now think of the difference between a curved map of the world on the surface of a globe and a flat map of the world. The sizes of some countries are distorted in the flat map, but countries adjacent on the globe stay adjacent on the flat map. We know the four color theorem applies to the flat version of the map, and since adjacency is preserved, we now know it applies to the globe version of the map as well. In fact, the four color theorem applies to any map on the surface of a sphere.
Using this fact, we can extend the four color theorem to the surfaces of even more 3-D objects. In topology, when an object can be stretched and bent into another object the two objects are said to be homeomorphic. Homeomorphic objects share many properties, including adjacency patterns on their surfaces. Spheres are homemorphic to cones, cylinders, and any convex polyhedron, including the cube, the pyramid and the other shapes mentioned above. Since the sphere is deformable into any of these objects, the four color theorem applies to all of their surfaces as well.
Why It's Interesting
The topic in and of itself is interesting. If you think about it, it would seem that you would need more than four colors to cover even a flat map. But really, only four colors are ever needed. If you think about any planar map with any amount of regions within it, it only needs four colors to cover it without any edges touching. That is interesting within itself.
More than four color theorems
Not all maps are planar, and not all surfaces can be colored with four or less colors. Maps on the surface of a Torus, a shape that looks like a donut, may need as many as 7 colors. The Mobius Strip can require as many as six colors. These surfaces which we can't easily imagine deforming into spheres require a different color theorem.
 |
 |
|
| While maps on a flat surface, cylinder, sphere, etc. require no more than 4 colors, maps on a torus, Mobius Strip, or related shape can require more. | ||
A formula called the Heawood Conjecture can be used to figure out the maximum possible number of colors needed to color a map on the surface of these other kinds of shape so that no two bordering regions are the same color. The formula is
where 
is the maximum possible number of necessary colors for a surface with an Euler Characteristic of 
. An Euler Characteristic is a topological property of a shape, a number that describes its structure regardless of how it is stretched or bent. Spheres and all the shapes they are homeomorphic to have an Euler Characteristic of 2. A torus has an Euler characteristic of 0. Applying Heawood's formula to the torus, we see that
Which means that, as mentioned earlier, a map on the surface of a Torus can require as many as 7 colors.
The only known exception to this formula is a surface called the Klein Bottle. The formula gives a maximum of 7 colors, when in actuality only 6 are ever needed to color a map the Klein Bottle.
For more on the Heawood Conjecture, check out this article.
How the Main Image Relates
My main image relates to the topics discussed here because the surface of the figure is covered with only four colors. No regions of the same color are touching each other, unless by a corner. This is an example of an extension of the Four Color Theorem to a 3D shape, which is what I looked into and experimented with.
It also relates because this is a picture of a game where the player puts cubes of four different colors in the board. The idea is to get the cubes of the same color to be spread out enough that one color block doesn't touch another block of the same color. This relates to my topics because it uses both 3D objects and the Four Color Theorem.
Teaching Materials
- There are currently no teaching materials for this page. Add teaching materials.
Related Links
Additional Resources
This is a link to the page on the torus. The torus is a counterexample to the Four Color Theorem's extension to many 3D objects. It is an interesting topic that shares the same ideas as my initial project.
This is another link to the Four Color Theorem Page. This is a good link for a little bit of background information.
References
Future Directions for this Page
If anyone can find an actual equation to work with my findings, that would be great. I have very little faith there is one to work with what I have, but if one is found, that would be greatly appreciated.
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.
[[Category:]]
