# Difference between revisions of "Four Color Theorem Applied to 3D Objects"

Four Color Theorem
Field: Graph Theory
Image Created By: [[Author:| ]]
Website: Chroma

Four Color Theorem

This picture is showing a basic understanding of the four color theorem using a bumpy 3D shape.

# Basic Description

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 can be covered in a minimum of four colors without any regions colored the same color touching unless by vertices, which is acceptable. If the regions of the same color touch by edges, then the Four Color Theorem is not being applied. 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

Chart of My Findings
[[Image:Sean Is Cool.png|Graph of My Finding [...]

Chart of My Findings
Graph of My Findings
Nets

## 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).

## Observations

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

Picture of Bipartite Graph

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)
Cycle Graph

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 topology

Just as this mug and torus can be morphed into each other, spheres can be deformed into cubes, cylinders, and many other 3-D shapes. As it turns out, the four color theorem survives this transformation.
These results make sense in the context of 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 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 , 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 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 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

$\gamma \left ( \chi \right ) = \bigg\lfloor \dfrac{7+\sqrt{49-24\chi}}{2} \bigg\rfloor$

where $\gamma \left ( \chi \right )$ is the maximum possible number of necessary colors for a surface with an Euler Characteristic of $\chi$. 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

$\gamma \left ( 0 \right ) = \bigg\lfloor \dfrac{7+\sqrt{49-0}}{2} \bigg\rfloor = \bigg\lfloor \dfrac{7+\sqrt{49}}{2} \bigg\rfloor = \bigg\lfloor \dfrac{7+7}{2} \bigg\rfloor = \bigg\lfloor \dfrac{14}{2} \bigg\rfloor = \big\lfloor 7 \big\rfloor$

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.

# How the Main Image Relates

My main image relates to the topics discussed here because this figure is covered with, at a minimum, four colors. No regions of the same color are touching each other, unless by a corner. This basically explains the definition of the Four Color Theorem which 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 3D objects as well as the Four Color Theorem.

# Teaching Materials

This is a link to the page on the Tori. This is the only known counterexample of the Four Color Theorem when using a 3D object. 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

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.