According to 5 Color Theorem, every planar graph is 5 colorable.
Lemma: Every planar graph is 6 colorable. This is also known as 6 Color Theorem.
Proof of 5 Color Theorem
We will prove it by mathematical induction.
Every planar graph vertices is 5 colorable.
Assume every planar graph vertices is 5 colorable.
In this step, we will show that if is true then is also true.
Suppose a planar graph G, . By 6 colorable theorem, we can say that G is 6 colorable. Suppose an edge u that is connected to 5 different colors.
Remove vertex u from the graph to obtain another planar graph G’, . G’ is 5 colorable (step 2). If we add u back to the graph, we will need 6 colors since it is connected to 5 different colors. We will show that all neighbors of u cannot have different colors.
Consider vertex v1 and v3. We have two situation.
Case 1: v1 and v3 are not connected through an alternating chain of blue-yellow vertices. In this case, we can easily change v1 to yellow by exchanging blue and yellow colors on some vertices without affecting the planarity of the graph. After that, we can assign blue to u.
Graph G is 5 colorable.
Case 2: In this case, there is an alternating blue-yellow chain between v1 and v3. Thus, exchanging v1 and v3 doesn’t matter. The graph will still be 6 colorable.
We need to show that even if v1 and v2 are connected through an alternating chain. The graph is still 5 colorable.
Now consider vertex v4 and v2. It is impossible to connect v4 and v2 (expect through u) since it will make the graph nonplanar which is contradictory. This implies no alternating color chain is possible between v2 and v4.
Since v2 and v4 are not connected through an alternating chain, we can exchange red and gray colors in component, v2 is connected to, and give red to u.
G is 5 colorable.
It also implies that if a graph is strictly 6 colorable, then it cannot be planar.
Therefore, if is true then is also true. Hence, by the principle of mathematical induction, every planar graph is 5 colorable.