GATE CS 2016 Set 2 Q03 — Graphs: Connectivity, Matching, Colouring

According to the Four Color Theorem, any planar graph can be vertex-colored using at most $4$ colors such that no two adjacent vertices share the same color.

To see why fewer than $4$ colors are not sufficient for any planar graph, consider the complete graph $K_4$:

• $K_4$ is a planar graph (it can be drawn in a plane without any edge crossings).
• Since every vertex in $K_4$ is connected to every other vertex, its chromatic number is $\chi(K_4) = 4$.

Thus, $3$ colors are not sufficient to color all planar graphs, making 4 the minimum number of colors sufficient to vertex-color any planar graph.