*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*