Four Color Theorem Applied to 3D Objects
|Four Color Theorem|
Four Color Theorem
- This picture shows an extension of the four color theorem to non-flat surfaces using a bumpy 3D shape.
- 1 Basic Description
- 2 A More Mathematical Explanation
- 3 Why It's Interesting
- 4 How the Main Image Relates
- 5 Teaching Materials
- 6 Related Links
- 7 References
- 8 Future Directions for this Page
In the picture, a 3D surface is shown being colored in 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 using my knowledge of this theorem, I can say that the upper block can be colored green, and the lower one be colored blue.
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.
A More Mathematical Explanation
- Note: understanding of this explanation requires: *Graph Theory
How I Conducted My Research
I conducted my experiment of applying the Four Color Theorem to 3D objects by drawing nets of the seven different objects I used. 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. Then I put my work into this chart and graph in the more mathematical section below.
The picture of the nets show the minimum number of colors used to cover each shape. The first one in each set is the 2D shape, and the second one is the 3D object (I applied to the coloring that one face touches multiple faces in the 3D form).
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, except by vertices which is acceptable (just not by edges).
After doing my experiment, I noticed a lot of different things within my work. I don't have a mathematical explanation yet for why I got the results I did, but I have connected it to graph theory and cycle graphs. 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 be colored the same color, always. However, there are not always multiple pairs of opposite sides.
- All the 2D nets are colored in 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 is the basis of my project on 3D objects applied to the Four Color Theorem.
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, but between the two sets, the vertices are 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 each blue point can connect to the green ones they share edges between but not to any of the blue ones without crossing other edges which would defeat the definition of a planar graph which 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 very 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 used to cover the 3D object than if there was a base number that was even. A base number is the number of vertices in the base of the object, as 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 to come out with only 2 two colors used. If you have a shape like a square, the colors of the vertices in the cycle graph would go: red, yellow, red, yellow (two colors). If there were five vertices as in a pentagon, it would 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 topologytopology.
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 3-D 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, 2-D 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 application of the Four Color Theorem to a 3-D 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 3-D objects as well as the Four Color Theorem.
- There are currently no teaching materials for this page. Add teaching materials.
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.
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.