A planar graph has a vertex of degree 5 or less The six colo

A planar graph has a vertex of degree 5 or less. The six color map theorem.

Solution

(a)

We will prove this statement by using a proof by contradiction. We will assume that G is planar and that all vertices of G have degree greater than or equal to 6. We know that the sum of the degrees of all verticies of a graph is equal to twice the number of edges. Since each vertex has a degree of 6 or greater, we obtain

6v 2e ..........(1)

3v e ..........(2)

where v is the number of vertices in the graph and e is the number of edges. If G is planar, then it must satisfy the Corollary of Euler’s Formula. Thus, the following must be true

e 3v 6

From (1) and (2) we get

3v e 3v 6 ............(3)

The inequality (3) is impossible since 3v > 3v 6.

Therefore, we have reached a contradiction to our assumption that all vertices of G have degree greater than or equal to 6. Hence, we conclude if a graph G is planar, then G has a vertex of degree at most 5.

(b)

Theorem..Let G be a planar graph. There exists a proper 6-coloring of G.

proof1..Let G be a the smallest planar graph (by number of vertices) that has no proper 6-coloring.

By Theorem , there exists a vertex v in G that has degree five or less. G \\ v is a planar graph smaller than G, so it has a proper 6-coloring.

Color the vertices of G \\ v with six colors; the neighbors of v in G are colored by at most five different colors.

We can color v with a color not used to color the neighbors of v, and we have a proper 6-coloring of G, contradicting the definition of G.

proof2..

We prove the result by induction on the number of vertices.

(Base case) Suppose we have a graph such that v 6. For v 6, we can give each vertex a different color and use 6 colors.

(Induction hypothesis) Now assume that any simple planar graph on v = n vertices can be properly colored with six colors.

Let G be any simple planar graph on v = n+1 vertices.we know that G must have some vertex w of degree 5. Remove w from G to form G . G has v = n vertices and we may apply our induction hypothesis to know it can be properly colored in 6 colors. Properly color G with 6 colors. Now, we can think of this as coloring all of G except w. But, since w has degree at most 5, one of the 6 colors will not be used for any of the neighbors of w and we can finish coloring G.