Graph Theory as the Base of Four Color Theorem

Graphs

Graph is a structure of a number of points and their connections within. The points are called Vertices (Vertex in singular). Connections are called Edges. Planner Graphs are those where the vertices can be placed in a way so that no edge will go over other edges. Planner graph can be drawn on a plane surface or a spherical surface. Let us consider the map of Dhaka district about making a graph. Dhaka has six administrative units which are named as 1, 2, 3, 4, 5 and 6 as shown on the Figure-1. These six regions are the six vertices. Edges are made according to the adjacent regions for each region. Thus, a planner graph is created (Figure-2). Now let us think of colors for the vertices of this graph keeping in mind that two adjacent regions will have different colors. In the example graph on Figure-1, six different colors are used for six regions. It was perhaps because of the design. According to Four Color Theorem, it could be colored with only three colors. Figure-2 shows the 3 color presentation.

dhk_map.JPG

dhk_colorA.jpg

Examples

Now the question is; can a place be divided into separate blocks so that 4 colors will not be enough, at least one more color is necessary? Let us take another comparatively complex example graph. Figure-3 shows a graph with 10 vertices. Vertex 4 and vertex 6 both have highest 6 edges. But still the whole graph can be colored with maximum 4 different colors. Coloring the regions by hand with different colors is a tedious job that can be done by computers by programming. In bare eyes it is often misunderstood that there would be more than four colors needed for coloring a map. But we are now convinced with the proven Four Color Theorem that maximum 4 colors are enough for coloring a map. Rather it is possible to color a map with 2 or 3 different colors sometimes. Figure-4 shows a such example graph where it seemed to be use of 5 colors on the left image. The image on right shows actually 4 colors are good enough to color the map. On the other hand it also considerable that if there is any biased or conditional situations so that some specific regions must be colored with some specific colors, then the Four Color Theorem will not be applicable. For example, someone may think of coloring six regions of Dhaka district with six different colors.

pic-1A.jpg

false-1.JPG

Last words

The example of such conditional graph is shown as Figure-5 where the condition is to color the regions named as ‘a’ must be of same color. Then the whole map must be colors with 5 different colors. Someone can still think of being famous overnight by proving the Four Color Theorem wrong in some ways!

conditional-1.JPG

Please also read the first part of this article History of Four Color Theorem.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s