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 
. We know that every planar graph satisfies the equation 
. On substituting the equations, we get
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.
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