13 ***Planar graphs***13.1 Euler’s formula and Kuratowski’s theorem 13.3 ***Graph dual****

13.2 Coloring of Planar graphs

Lemma 13.10.

Every planar graph has a vertex of degree at most $5$ .

Proof.

If every vertex has degree at least $6$ , then $2e\geq 6v$ which contradicts Lemma 13.6. ∎

Using the above lemma and induction, one can prove that a planar graph is $5$ -colorable. But we can do better with a little more arguments.

Theorem 13.11.

Every planar graph is $5$ -colorable.

Proof.

The theorem is trivially true for graphs with at most $5$ vertices. By induction, we assume that the theorem holds for all graphs with at most $n$ vertices.

Let $G$ be a planar graph with $n+1$ vertices. By Lemma 13.10, there is a vertex $v$ of degree at most $5$ . Choose the same.

CASE 1 : If $deg(v)<5$ , then by induction $G-v$ is $5$ -colorable and we can assign $v$ a color not assigned to any of its (at most $4$ ) neighbours.

CASE 2 : Suppose $deg(v)=5$ . Let $N(v)=\{v_{1},\ldots,v_{5}\}$ . Since $K_{5}$ is not planar, $v_{1},\ldots,v_{5}$ cannot form a complete graph and hence WLOG, assume that $v_{1}\nsim v_{2}$ . Construct a new planar graph $G^{\prime}$ by contracting the edge $(v_{1},v)$ and denoting the new vertex by $v^{\prime}$ . Further construct a planar graph $G^{\prime\prime}$ by contracting the edge $(v^{\prime},v_{2})$ and denoting the new vertex $v^{\prime\prime}$ . Since $G^{\prime\prime}$ has $n-1$ vertices and is planar, it is $5$ -colorable.

To construct a $5$ -coloring on $G$ : Assign the same colors as in $G^{\prime\prime}$ to all vertices in $G$ except $v,v_{1},v_{2}$ . Further assign the color of $v^{\prime\prime}$ to $v_{1}$ and $v_{2}$ . Now, $N(v)$ has been colored using only $4$ colors and so assign the $5$ th color to $v$ . ∎