Question

Show that every planar graph Gcan be colored using five or fewer colors. (Hint:Use the hint provided for Exercise 40.)

The famous Art Gallery Problem asks how many guards are needed to see all parts of an art gallery, where the gallery is the interior and boundary of a polygon with nsides. To state this problem more precisely, we need some terminology. A point x inside or on the boundary of a simple polygon Pcoversor seesa point yinside or on Pif all points on the line segment xy are in the interior or on the boundary of P. We say that a set of points is a guarding setof a simple polygon Pif for every point yinside Por on the boundary of Pthere is a point xin this guarding set that sees y. Denote by G(P)the minimum number of points needed to guard the simple polygon P. The art gallery problemasks for the function g(n), which is the maximum value of G(P)over all simple polygons with nvertices. That is, g(n)is the minimum positive integer for which it is guaranteed that a simple polygon with nvertices can be guarded with g(n)or fewer guards.

Short answer

It is proved that every planar graph G can be colored using five or fewer colors.

Step-by-step solution

Given Information

Planar graph G

Concept used

Theorem 5.10. 6 (Five Color Theorem) states that Every planar graph can be colored with 5 colors. This theorem is a result from graph theory and tells that given a plane separated into regions, such as a political map of the counties of a state, the regions can be colored using no more than five colors in such a way that no two adjacent regions receive or can have the same color.

Proving that every planar graph G can be colored using five or fewer colors

We use Induction on the number of vertices of the graph. Every graph with five or fewer vertices can be colored with five or fewer colors, as each vertex can get a different color. That takes care of the basis case(s).

So, we assume that all graphs with k vertices can be 5-colored and consider a graph G with k+1 vertices.

By Corollary in Section 10.7, G has a vertex v with degree at most 5.

Remove v to form the graph G. Since, G has only k vertices, we 5-color it by the Inductive hypothesis.

If the neighbor of v does not use all five colors, then we can 5-color G by assigning to v a color not used by any of its neighbors.

The difficulty arises if v has five neighbors, each has a different color in 5-coloring of ‘G’.

Suppose that the neighbor of v, when considered in clockwise order around v are a, b, c, m and p (This order is determined by the clockwise order of the curves representing the edges incident to v).

Assume that the colors of the neighbor are azure, blue, chartreuse, magenta and Purple respectively. Consider the azure-chartreuse sub graph (i.e. the vertices in the G colored azure or chartreuse and all the edges between them).

If a and c are not in the same component of this graph, then in the component containing a we can interchange these two colors (makes the azure vertices chartreuse and vice-versa), and G will still be properly colored.

That makes the chartreuse, so we can now color v azure, and G has been properly colored. If a and c in the same component, then there is a path of vertices alternately colored azure and chartreuse joining a and c.

This path together with edges av and vc divides the plane into two regions, with b in one of them and m in the other.

If we now interchange blue and magenta on all the vertices in the same region as b, we will still have a proper coloring of ‘G’, but now blue is available for v. In this case too, we found a proper coloring of G.

This completes the Inductive step, and the theorem is proved.

Thus, every planar graph G can be colored using five or fewer colors.