Question

Show that every planar graph \(G\) can be colored using six or fewer colors.

Short answer

Every planar graph \(G\) can be colored using six or fewer colors.

Step-by-step solution

Given information

Given is \(G - color\).

Definition and formula to be used

A\(k - tuple\)coloring of a graph\(G\)is an assignment of a set of\(k\)different colors to each of the vertices of\(G\)such that no two adjacent vertices are assigned a common color.

\({X_k}\left( G \right)\)represents that\(G\)has\(k - tuple\)coloring using\(n\)different colors.

Solution

Let\(P\left( n \right)\)be “\(G\)can be colored using six or fewer colors when \(G\) contains\(n\)vertices”.

Let\(P\left( k \right)\)be true for\(n = 1,2,3,4,5,6\).

Therefore,\(P\left( 1 \right),P\left( 2 \right),P\left( 3 \right),P\left( 4 \right),P\left( 5 \right),P\left( 6 \right)\)be true.

Now, we need to prove that\(P\left( {k + 1} \right)\)is true.\(G'\)is the graph that can be formed from graph\(G\)with vertex\(v\)removed. The same way as the vertices in\(G'\). We colour the vertices in\(G\). The vertex\(v\)is assigned to be one of the colors of the other vertices, which is possible as\(v\)is connected to at the most\(5\)other vertices and thus there is\(1\)colour that does not occur in the adjacent vertices of\(v\).

Therefore,\(P\left( {k + 1} \right)\)is true.

And \(P\left( n \right)\) is true for all positive integer of \(n\).