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:
Segundo o Teorema de Kuratowski, um grafo planar não apresenta nem o K5 nem o grafo bipartido K3,3 como subgrafos. A prova de que o K3,3 não é planar pode ser feita de duas formas: por indução e por construção, enquanto a do K5 é feita apenas por construção.
Representação do K5 - Grafo completo com 5 vérticesRepresentação do K3,3 - Grafo bipartido completo com 6 vértices
Não é possível redesenhar estes grafos sem que suas arestas se cruzem.