6 Color Theorem

According to 6 Color Theorem, every planar graph is 6 colorable.

Lemma: For any simple planar graph G, the minimum degree is less than equal to 5.

Proof: The average degree D of a graph is D = 2e/v . We know that every planar graph satisfies the equation  e \leq 3v - 6\;(v \geq 3). On substituting the equations, we get
D \leq 2(3v - 6)/v
D \leq 6 - 12/v
We\;know,\;6 - 12/v<6\;(for\;v>0)
D < 6
D \leq 5
Thus, the average degree of a planar graph is less than equal to 5. This implies the minimum degree of a planar graph is also less than equal to 5.

Proof of 6 Color Theorem

We need to prove that every planar graph is 6 colorable. We will prove it using mathematical induction.

Step 1
Every planar graph with vertices v <= 6 is 6 colorable since we can assign a unique color to every vertex.

Step 2
Assume all planar graphs with v = k vertices to be 6 colorable.

Step 3
We need to prove that if n = k is 6 colorable then n = k + 1 is also 6 colorable.
Suppose a planar graph G with v = k + 1 vertices. We already proved that the minimum degree of a planar graph is less than 6. Let u be the vertex with the minimum degree. Remove vertex u from G. Removing vertices from a planar graph does not make it nonplanar. Thus, G’ is also planar.

six color theorem proof by mathematical induction

G’ is a planar graph with v = k vertices. G’ is 6 colorable (from Step 2). Suppose we want to insert vertex u back to G’ to get G. In the worst case, the degree of u will be 5 and all the neighbors will be of a different color. Even in the worst case, we still have 1 color left that we can assign to u. Thus, graph G is 6 colorable.

In this way, we can show that every planar graph with v = k + 1 vertices is 6 colorable if every planar graph v = k is 6 colorable.

Therefore, by the principle of mathematical induction, we can say that the statement that every planar graph is 6 colorable is true for all v >= 1.

Leave comment if you face any problem

Leave a Comment

Your email address will not be published. Required fields are marked *