Grafos

Teorema 3.27 ( Kuratowski, 1930 ). Um grafo é planar se e só se não tiver nenhum subgrafo que seja uma subdivisão de ou .

Teorema 3.28. Um grafo é planar se e só se não tem nenhum subgrafo que admite uma contração para ou .

Proposição 3.30. Seja um subgrafo de um grafo simples . Então . Em particular, se tiver algum subgrafo isomorfo a um grafo completo , para algum , então .

Os vértices a , b , c induzem um subgrafo isomorfo . Logo Atribuindo a a(cor1),a b e a d(cor 2) e a c e e a (cor 3),obtemos uma de . Logo

Teorema 3.31. Seja um grafo simples com . Então se e só se é bipartido.

é bipartido
Note que se o ,então
( mostrar fig. Geogebra ApresTe3.31A )
Suponhamos que é uma bipartição de .
Então se atribuirmos aos vértices de a cor e aos vértices de a cor , obteremos uma de .
( mostrar fig. Geogebra ApresTe3.31B )
Logo,

Agora, supondo que cores e e
Temos que é uma bipartição de pois, como todos os vértices de têm a mesma cor, não podem ser adjacentes entre si; o mesmo para os vértices de .
Logo, é bipartido

Uma outra caracterização dos grafos planares envolve a noção de contração de uma aresta. A contração da aresta no grafo é o grafo que se obtém retirando a aresta a e identificando as suas extremidades.
Exemplo: A contração de uma aresta de
(Figura pasta contração de arestas)

Problema da coloração de mapas em termos de grafos
Escolhemos um vértice no interior de cada região do interior do mapa e unimos dois vértices por uma aresta se as regiões correspondentes tiverem uma fronteira em comum. Obtemos assim uma representação planar de um grafo simples , dito o grafo dual do mapa (passamos assim do concreto para o abstrato).Desta forma a coloração do mapa corresponde a coloração dos vértices de de forma que vértices adjacentes tenham cores distintas.
Seja um grafo simples uma coloração dos vértices de é uma atribuição de uma cor a cada vértice de