Grafo planar

Planar no significa que todo dibujo del grafo sea sin cruces, sino que existe al menos uno. Un mismo grafo puede dibujarse con cruces y, aun así, ser planar si se reacomoda. Cuando se fija un dibujo sin cruces, las aristas dividen el plano en regiones llamadas caras; la región infinita que rodea todo cuenta como una cara más, la exterior.

El resultado central es la fórmula de Euler: en un dibujo plano de un grafo conexo, \(v-e+f=2\). Para un grafo con \(c\) componentes conexas la fórmula se convierte en \(v-e+f=1+c\). De ella se deduce que un grafo simple planar con \(v\ge3\) cumple \(e\le 3v-6\), porque cada cara está limitada por al menos tres aristas y cada arista bordea dos caras. Si además no hay triángulos, cada cara tiene al menos cuatro aristas y entonces \(e\le 2v-4\).

Esas cotas permiten probar que un grafo no es planar: \(K_5\) tiene 10 aristas y \(3\cdot5-6=9\), y \(K_{3,3}\) tiene 9 aristas y \(2\cdot6-4=8\). Ojo con el recíproco: cumplir la cota no garantiza planaridad, como muestra \(K_{3,3}\) frente a \(3v-6=12\). El teorema de Kuratowski completa el cuadro: un grafo es planar exactamente cuando no contiene una subdivisión de \(K_5\) ni de \(K_{3,3}\). El problema clásico de las tres casas y los tres servicios es justamente \(K_{3,3}\).