Grafo planar

Na teoria dos grafos, um grafo planar é um grafo que pode ser representado no plano de tal forma que suas arestas não se cruzem. Por exemplo, os dois grafos seguintes são planares:

       

Teorema de Kuratowski

Segundo o Teorema de Kuratowski, um grafo planar não pode apresentar nem o grafo completo K₅ nem o grafo bipartido K_3,3 como subgrafos. A prova de que o K_3,3 não é planar pode ser feita de duas formas: por indução e por construção, enquanto a do K₅ é feita apenas por construção.

Não é possível redesenhar estes grafos sem que suas arestas se cruzem.

• 

  Representação do K5 (um grafo completo com 5 vértices).

• 

  Representação do K3,3 (um grafo bipartido completo com 6 vértices).

Teorema das quatro cores

O teorema das quatro cores afirma que qualquer grafo planar é 4-colorível (ou 4-partível).

Ver também

• Teorema de Kuratowski
• Teorema das quatro cores