Planaridade

Um grafo G=(V,E) é planar quando existe um desenho no plano em que as arestas só se encontram em vértices. Esse desenho, já fixo, é um grafo plano: pontos, curvas e as faces — regiões abertas que o desenho recorta no plano.

A fórmula V−E+F, o teto de arestas e o critério estrutural deste tópico partem dessa imersão.

As páginas se agrupam em três blocos. O primeiro decide se alguma imersão existe: um desenho sem cruzamentos prova que G é planar; um desenho com cruzamentos não prova o contrário; m>3n−6 recusa, m≤3n−6 ainda não decide.

O segundo conta as faces de um desenho já feito. No grafo plano conexo, V−E+F=2 incluindo a face ilimitada, e daí sai E≤3V−6; com C componentes que compartilham essa face, o invariante é C+1.

O terceiro procura um subgrafo que seja subdivisão de K₅ ou de K₃,₃: arestas do completo ou do bipartido 3+3 esticadas por vértices de grau 2.

Comparar m com 3n−6, sem contar faces, está em Grafos Planos. Obter E≤3V−6 a partir de V−E+F=2 e de 2E≥3F está em Fórmula de Euler.

Exibir um desenho sem cruzamentos prova planaridade em Grafos Planos. Exibir uma subdivisão de K₅ ou de K₃,₃ prova o contrário em Teorema de Kuratowski.

K₅ tem 10>9, então o teto em Grafos Planos já recusa. K₃,₃ tem 9≤12: a subdivisão está em Teorema de Kuratowski.