Teorema

Todo grafo planar pode ser colorido com $5$ cores.

Demonstração:

Tomemos $G$ um grafo planar com $n \geq 6$ vértices e $m$ arestas. Sabemos que o grafo possui no máximo $3n - 6$ arestas. Assim iremos por indução supor que todo grafo com menos de $n$ vértices possui $5$-coloração.

$$d(G) = \frac{\sum(d(v))}{n} =\frac{2m}{n} \leq \frac{2(3n - 6)}{n} < 6$$

Tomemos $v$ um vértice de $G$ de grau menor ou igual a $5$. Se $d(v) < 5$ então este vértice $v$ seria a quinta cor; se $d(v) = 5$, todos os vértices adjacentes de $v$ possuem cores distintas.

Tome $D$ um disco em torno de $v$, pequeno a ponto de apenas conter linhas retas de segmentos que contém $v$, agora vamos enumerar estes segmentos da forma que aparecem dentro do disco como $s_1,\dots,s_5$ e $v_i$ o vértice contendo $s_i$, como na figura a seguir.

Vamos mostrar que todo caminho $P$ conectando $v_1 - v_3$ separa $v_2$ de $v_4$. Isso ocorre apenas no caso que em o ciclo $C = vv_1Pv_3v$ separa $v_2$ de $v_4$, provamos que isso é verdade mostrando que $v_2$ e $v_4$ estão em faces diferentes. Tome $x_2$ de $s_2$ em $D$ e $x_4$ de $s_4$ em $D$, assim $D \setminus (s_1 \cup s_3) \subset \mathbb{R}^2 \setminus C$ pode ser conectado por um polígono de $x_2$ a $x_4$ , assim pelo Teorema da curva Jordan para polígonos, $x_2$ e $x_4$, estão em faces diferentes do ciclo $C$.

Tomando agora $i,j \in \{1,\dots,5\}$, tome $H_{i,j}$ os subgrafos de $G \setminus v$ induzidos. Podemos supor que a componente $C_1$ de $H_{1,3}$ contém $v_1$ e $v_3$. Inclusive, se trocarmos as cores de $1$ e $3$ em todos os vértices de $C_1$, obtemos uma nova $5$-coloração de $G \setminus v$.

Se $v_3 \notin C_1$, então $v_1$ e $v_3$ são ambos coloridos com $3$ nessa nova coloração, e podemos então pintar $v$ com a cor $1$. Assim $H_{1,3}$ contém uma caminho $P$ de $v_1 - v_3$, como mostrado antes $P$ separa $v_2$ e $v_4$ em $G \setminus v$. Já que $P \cap H_{2,4} = \emptyset$, por isso $v_2$ e $v_4$ estão em faces diferentes de $H_{2,4}$. Na componente contendo $v_2$ , trocamos as cores $2$ e $4$ e trocamos $v_2$ com a cor $4$, assim $v$ não possui vizinhos coloridos com $2$, e podemos colorí-lo com essa cor.

$\square$