Index

There are many interesting applications related to the geometries we have seen thus far. One of the most famous applications of graph theory in particular is the idea of the coloring of graphs.

The problems surrounding the coloring of graphs began in 1852 by a law student named Francis Guthrie who proposed the following question: Suppose there is a map and the various countries are colored such that no two countries which share a common border have the same color. What is the minimum number of colors needed? Two countries which do not share a border can be the same color. In addition, if two countries meet only at a corner, they may also be the same color. Guthrie proposed that every map could be colored with four or fewer different colors.

After drawing several examples, you will not be able to produce a counterexample. However, The Four Color Theorem took many years to prove. It was one of the most famous unsolved mathematical problems for nearly 100 years! The full proof was computer-assisted and is millions of pages long, if written out!!

So what does this have to do with graph theory? It turns out that each country can be assigned a vertex and if the countries meet at a border, they are joined by an edge. Any two vertices that are connected by an edge must be a different color.

Notice that any graph created this way will be planar (created on a plane).

Definintion: A planar graph is a graph in which no edges are allowed to intersect away from the vertices.

Often graphs that appear not to be planar can simply be reconstructed such that no two edges intersect aside from at the vertices. An example of a nonplanar graph is the complete graph on 5 vertices.

So, it follows that the Four Color Theorem is equivelant to stating that the chromatic number of a planar graph is not greater four.

Definintion:The chromatic number X(G) of a graph G is the minimum number of colors required to "good color" the vertices of G. A good coloring of a graph G occurs when there are no edges having end vertices of the same color

In a complete graph K_n, the chromatic number will always be n, the number of vertices. This is true because all vertices are connected to all other vertices by an edge. Notice that no complete graph will ever be planar except for the complete graphs on 4 or fewer vertices.

The chromatic number of a graph G is 1 only when G has no edges.

Recall from Problem 29 the defininition of a bipartite graph. Another interesting property of bipartite graphs is that they will always have chromatic number 2. It is fairly trivial to see why this is the case. None of the vertices of V₁ are connected to any of the other vertices of V₁. The same is true for V₂. So we can color all vertices of V₁ a given color and all vertices of V₂ another color.

PROBLEM 30: (a) Show that for an graph G with n vertices, . (b): If G is the smallest graph (meaning it has the least amount of vertices) with chromatic number n (n >1) show that G has no vertices of degree less that n - 1. Will this be true for any graph with chromatic number n? Solutions