5 Color Theorem | SlayStudy

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.

Step 1
Every planar graph $0\leq v \leq5$ vertices is 5 colorable.

Step 2
Assume every planar graph $v=k$ vertices is 5 colorable.

Step 3
In this step, we will show that if $v=k$ is true then $v=k+1$ is also true.

Suppose a planar graph G, $v=k+1$ . 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’, $v=k$ . 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.

subgraph of g showing the vertex connected to 5 different colors

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.

if no 2 vertices are not connected by alternating chain then g is 5 colorable

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.

alternate color chain between 2 vertices

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.

two non adjacent vertices cannot form chain of alternating color

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.

every planar graph is 5 colorable. 5 color theorem proved.

G is 5 colorable.

It also implies that if a graph is strictly 6 colorable, then it cannot be planar.

Therefore, if $v=k$ is true then $v=k+1$ is also true. Hence, by the principle of mathematical induction, every planar graph is 5 colorable.

Proof of 5 Color Theorem

Leave a Comment Cancel Reply