Grafos Planares y Steinitz
No todo grafo es un poliedro. El teorema de Steinitz establece la frontera exacta.
1. Grafos Planares
Un grafo \(G\) es planar si puede dibujarse en el plano de modo que sus aristas no se crucen, salvo en los vertices que comparten. Tal dibujo se denomina inmersion planar o grafo plano. La diferencia es sutil pero importante: "planar" es una propiedad intrinseca del grafo; "plano" se refiere a un dibujo concreto sin cruces.
El ejemplo mas inmediato es \(K_4\), el grafo completo de 4 vertices. Basta dibujar un triangulo con un punto interior conectado a los tres vertices del triangulo: las 6 aristas no se cruzan. De hecho, \(K_4\) es el grafo esqueleto del tetraedro.
Los cinco grafos platonicos son todos planares. Esto no es una coincidencia: provienen de poliedros convexos tridimensionales, y todo poliedro convexo puede proyectarse al plano desde un punto cercano a una cara. La proyeccion estereografica o la proyeccion de Schlegel (que veremos en la seccion 6) producen una inmersion planar donde una cara se convierte en el contorno exterior.
La pregunta central de esta leccion es la inversa: dado un grafo planar, cuando proviene de un poliedro convexo? El teorema de Steinitz dara la respuesta exacta.
2. La Formula de Euler para Grafos Planares
En el Modulo 2 demostramos la formula de Euler para poliedros. Ahora la extendemos a todo grafo planar conexo. Si \(G\) es un grafo plano conexo con \(V\) vertices, \(E\) aristas y \(F\) caras (incluyendo la cara exterior, la region no acotada), entonces:
$$ V - E + F = 2 $$La demostracion procede por induccion sobre el numero de aristas \(E\).
Caso base. Si \(G\) es un arbol (grafo conexo sin ciclos), entonces \(E = V - 1\) y hay una unica cara (la cara exterior), asi que \(F = 1\). Se verifica: \(V - (V-1) + 1 = 2\).
Paso inductivo. Si \(G\) no es un arbol, contiene al menos un ciclo. Elegimos una arista \(e\) que pertenece a un ciclo. Al eliminar \(e\), el grafo sigue siendo conexo (porque los extremos de \(e\) estan conectados por el resto del ciclo), pero las dos caras que bordean \(e\) se fusionan en una sola. Asi, \(V\) no cambia, \(E\) disminuye en 1 y \(F\) disminuye en 1, dejando \(V - E + F\) invariante. Por hipotesis de induccion, el resultado vale para el grafo reducido, y por tanto tambien para \(G\).
Esta formula generaliza la relacion poliedrica a todos los grafos planares conexos, no solo a los que provienen de poliedros.
3. Cotas de Aristas
La formula de Euler, combinada con un conteo de incidencias cara-arista, produce desigualdades que limitan la densidad de un grafo planar. En un grafo plano, cada cara esta bordeada por al menos 3 aristas, y cada arista bordea exactamente 2 caras. Sumando sobre todas las caras:
$$ 2E \geq 3F \implies F \leq \frac{2E}{3} $$Sustituyendo en la formula de Euler \(V - E + F = 2\):
$$ V - E + \frac{2E}{3} \geq 2 \implies E \leq 3V - 6 $$Esta es la cota fundamental de aristas para grafos planares. Si un grafo tiene mas de \(3V - 6\) aristas, no puede ser planar.
Para grafos sin triangulos (cintura \(\geq 4\)), cada cara tiene al menos 4 aristas en su frontera, lo que da \(2E \geq 4F\) y una cota mas restrictiva:
$$ E \leq 2V - 4 $$Aplicacion a \(K_5\). El grafo completo \(K_5\) tiene \(V = 5\) y \(E = \binom{5}{2} = 10\). La cota da \(3(5) - 6 = 9 < 10\). Conclusion: \(K_5\) no es planar.
Aplicacion a \(K_{3,3}\). El grafo bipartito completo \(K_{3,3}\) tiene \(V = 6\), \(E = 9\) y es libre de triangulos. La cota para grafos sin triangulos da \(2(6) - 4 = 8 < 9\). Conclusion: \(K_{3,3}\) no es planar.
4. El Teorema de Kuratowski (1930)
Las cotas de aristas demuestran que \(K_5\) y \(K_{3,3}\) no son planares, pero no caracterizan completamente la planaridad. El teorema de Kuratowski proporciona una condicion necesaria y suficiente.
Una subdivision de un grafo \(H\) se obtiene reemplazando aristas de \(H\) por caminos (insertando vertices de grado 2 en las aristas). Un grafo \(G\) contiene una subdivision de \(H\) si algun subgrafo de \(G\) es isomorfo a una subdivision de \(H\).
El teorema establece:
$$ G \text{ es planar} \iff G \text{ no contiene subdivision de } K_5 \text{ ni de } K_{3,3} $$Este resultado es notable porque reduce la pregunta de planaridad a la deteccion de exactamente dos obstrucciones minimales. Toda no-planaridad proviene, en ultima instancia, de una copia "escondida" de \(K_5\) o \(K_{3,3}\).
Un resultado equivalente es el teorema de Wagner (1937), que reemplaza "subdivision" por "menor topologico": un grafo es planar si y solo si no tiene a \(K_5\) ni a \(K_{3,3}\) como menor. Un menor se obtiene contrayendo aristas (fusionando sus extremos) ademas de eliminar vertices y aristas. Los dos criterios son equivalentes para la planaridad, aunque la nocion de menor es mas general y central en la teoria de Robertson-Seymour.
5. El Teorema de Steinitz (1922)
La planaridad es necesaria pero no suficiente para que un grafo sea el esqueleto de un poliedro convexo. Se requiere ademas una condicion de conectividad. Un grafo \(G\) es \(k\)-conexo si tiene mas de \(k\) vertices y al eliminar cualquier conjunto de \(k-1\) vertices (y sus aristas incidentes) el grafo resultante sigue siendo conexo.
La 3-conectividad significa que no se puede desconectar el grafo eliminando 1 o 2 vertices. Intuitivamente, el esqueleto de un poliedro convexo es "robusto" topologicamente: ningun par de vertices es un cuello de botella.
El teorema de Steinitz establece:
$$ G \text{ es esqueleto de un politopo convexo 3D} \iff G \text{ es 3-conexo y planar} $$Los cinco grafos platonicos son todos 3-conexos. De hecho, son \(\delta\)-conexos, donde \(\delta\) es el grado minimo: el tetraedro y el cubo son 3-conexos, el octaedro es 4-conexo, y el icosaedro es 5-conexo. Esto confirma, via Steinitz, que todos provienen de poliedros convexos.
El teorema de Steinitz es el puente definitivo entre la teoria de grafos y la geometria poliedrica: traduce una propiedad geometrica (ser esqueleto de un politopo convexo) en propiedades puramente combinatorias (planaridad y 3-conectividad).
Los dos grafos no planares minimales: \(K_5\) y \(K_{3,3}\). Ninguno es esqueleto de un poliedro convexo.
6. Diagramas de Schlegel
Un diagrama de Schlegel es una proyeccion de un poliedro convexo 3D al plano, realizada desde un punto situado ligeramente fuera del centro de una cara. La cara elegida se convierte en el contorno exterior del diagrama, y las demas caras aparecen como regiones interiores.
El resultado es una inmersion planar del grafo esqueleto donde la estructura combinatoria (vertices, aristas y caras) se preserva completamente. Cada diagrama de Schlegel demuestra constructivamente que el grafo del poliedro es planar.
Cubo. El diagrama de Schlegel del cubo consiste en un cuadrado exterior (la cara de proyeccion), un cuadrado interior mas pequenio (la cara opuesta), y cuatro aristas que conectan los vertices correspondientes. Las seis caras del cubo son visibles: la exterior, la interior y cuatro trapecios laterales.
Dodecaedro. El diagrama de Schlegel del dodecaedro tiene un pentagono exterior y una estructura concentrica de pentagonos anidados. Las 12 caras pentagonales son todas visibles como regiones del diagrama.
Los diagramas de Schlegel son una herramienta esencial para estudiar la combinatoria de poliedros: permiten "aplanar" la estructura tridimensional sin perder informacion topologica.
Diagramas de Schlegel del cubo (izquierda) y del dodecaedro (derecha)
Ejercicios
1. Verifica la cota \(E \leq 3V - 6\) para los cinco grafos platonicos. Cuales alcanzan la igualdad?
2. El grafo de Petersen tiene \(V = 10\), \(E = 15\) y cintura 5. Demuestra que satisface \(E \leq 3V - 6\) pero viola la cota \(E \leq \frac{5}{3}V - \frac{10}{3}\) (la cota para cintura \(\geq 5\)). Que implica esto sobre su planaridad?
3. Demuestra que todo grafo planar tiene al menos un vertice de grado \(\leq 5\), usando la cota \(E \leq 3V - 6\) y el lema del apreton de manos.
4. Dibuja el diagrama de Schlegel del octaedro. Cuantas caras triangulares son visibles (incluyendo la cara exterior)?
5. Verifica que los cinco grafos platonicos son 3-conexos. Para el tetraedro, demuestra que al eliminar cualquier par de vertices el grafo resultante sigue siendo conexo.
LAB: Diagramas de Schlegel
Selecciona un poliedro para ver su diagrama de Schlegel (inmersion planar). Arrastra vertices para reorganizar. Haz clic en un vertice para resaltar sus vecinos.