En la combinatoria poliédrica, una rama de las matemáticas, el teorema de Steinitz es una caracterización de los grafos no dirigidos formados por las aristas y los vértices de poliedros convexos tridimensionales: son exactamente los grafos planares de 3 vértices conectados. Es decir, todo poliedro convexo forma un grafo plano de 3 vértices, y todo grafo plano de 3 vértices puede representarse como el grafo de un poliedro convexo. Por esta razón, los grafos planos de 3 conexiones también se conocen como grafos poliédricos.
Este resultado proporciona un teorema de clasificación para los poliedros convexos tridimensionales, algo que no se conoce en dimensiones superiores. Proporciona una descripción completa y puramente combinatoria de los grafos de estos poliedros, permitiendo que otros resultados sobre ellos, como el teorema de Eberhard sobre la realización de poliedros con determinados tipos de caras, se demuestren más fácilmente, sin referencia a la geometría de estas formas. Además, se ha aplicado en el dibujo de grafos, como una forma de construir visualizaciones tridimensionales de grafos abstractos. Branko Grünbaum ha llamado a este teorema «el resultado más importante y profundo conocido sobre los 3-politopos».
El teorema aparece en una publicación de 1922 de Ernst Steinitz, que le da nombre. Puede demostrarse por inducción matemática (como hizo Steinitz), hallando el estado de energía mínima de un sistema de muelles bidimensional y trasladando el resultado a tres dimensiones, o utilizando el teorema del empaquetamiento de circunferencias. Se conocen varias extensiones del teorema, en las que el poliedro que realiza un grafo dado tiene restricciones adicionales; por ejemplo, todo grafo poliédrico es el grafo de un poliedro convexo con coordenadas enteras, o el grafo de un poliedro convexo todas cuyas aristas son tangentes a una semiesfera común.
Definiciones y enunciado del teorema miniaturadeimagen|270x270px|Iluminar el esqueleto de un poliedro convexo desde una fuente de luz cercana a una de sus caras hace que sus sombras formen un diagrama de Schlegel plano. Un grafo no dirigido es un sistema de vértices y aristas, cada una de las cuales conecta dos de los vértices. Como es habitual en la teoría de grafos, a efectos del teorema de Steinitz estos grafos se limitan a ser finitos (los vértices y las aristas son conjuntos finitos) y simples (no hay dos aristas que conecten los dos mismos vértices, y ninguna arista conecta un vértice consigo misma). A partir de cualquier poliedro se puede formar un grafo, haciendo que los vértices del grafo correspondan a los vértices del poliedro y conectando dos vértices cualesquiera del grafo mediante una arista siempre que los dos vértices correspondientes del poliedro sean los puntos extremos de una arista del poliedro. Este grafo se conoce como el esqueleto del poliedro.Más técnicamente, este gráfico es el 1-esqueleto; véase Grünbaum (2003), p. 138, y Ziegler (1995), p. 64.
Un grafo es plano si se puede dibujar con sus vértices como puntos en el plano euclídeo, y sus aristas como curvas que conectan estos puntos, de forma que no se crucen dos curvas de arista y que el punto que representa un vértice se encuentre en la curva que representa una arista sólo cuando el vértice es un extremo de la arista. Por el teorema de Fáry, todo dibujo plano puede enderezarse de modo que las curvas que representan las aristas sean segmentos rectos. Un grafo está 3-conectado si tiene más de tres vértices y, tras la eliminación de dos de sus vértices cualesquiera, cualquier otro par de vértices permanece conectado por un camino. El teorema de Steinitz afirma que estas dos condiciones son necesarias y suficientes para caracterizar los esqueletos de los poliedros convexos tridimensionales: un grafo dado es el gráfico de un poliedro tridimensional convexo, si y sólo si es plano y está conectado por 3 vértices.
Pruebas miniaturadeimagen|Ilustración de la demostración del teorema de Balinski, que muestra el conjunto cero de una función lineal (azul) que pasa por dos vértices dados (amarillo) y los caminos del método simplex que conectan el resto del gráfico (verde). Una de las direcciones del teorema de Steinitz (la más fácil de demostrar) afirma que el grafo de todo poliedro convexo es plano y está conectado por 3 puntos. Como se muestra en la ilustración, la planaridad puede demostrarse utilizando un diagrama de Schlegel: si se coloca una fuente de luz cerca de una cara del poliedro, y un plano en la otra cara, las sombras de las aristas del poliedro formarán un grafo planar, incrustado de tal manera que las aristas son segmentos de línea recta. La 3-conectividad de un grafo poliédrico es un caso especial del teorema de Balinski según el cual el grafo de cualquier dimensional politopo convexo está conectado. La conectividad del grafo de un politopo, después de eliminar cualquier de sus vértices, puede demostrarse eligiendo un vértice más , encontrando una función lineal que sea cero en el conjunto resultante de vértices y siguiendo los caminos generados por el método simplex para conectar cada vértice con uno de los dos vértices extremos de la función lineal, con el vértice elegido conectado a ambos.
La otra dirección, más difícil, del teorema de Steinitz afirma que todo grafo plano de 3 conexiones es el grafo de un poliedro convexo. Existen tres enfoques estándar para esta parte: pruebas por inducción, elevación de embebidos bidimensionales de Tutte a tres dimensiones mediante la correspondencia Maxwell-Cremona y métodos que utilizan el teorema del empaquetamiento de circunferencia para generar un poliedro canónico.
Inducción miniaturadeimagen|440x440px|ΔY- e YΔ-transformación de un poliedro Aunque la prueba original de Steinitz no se expresó en términos de teoría de grafos, puede reescribirse en esos términos y consiste en encontrar una secuencia de transformaciones ΔY- e YΔ que reducen cualquier grafo plano de 3 conexiones a , el grafo del tetraedro. Una transformación Y elimina un vértice de grado tres de un grafo, añadiendo aristas entre todos sus vecinos anteriores si esas aristas no existían ya; la transformación inversa, una transformación ΔY, elimina las aristas de un triángulo de un grafo y las sustituye por un nuevo vértice de grado tres adyacente a los mismos tres vértices. Una vez encontrada una secuencia de este tipo, puede invertirse y convertirse en operaciones geométricas que construyan paso a paso el poliedro deseado partiendo de un tetraedro. Cada transformación Y de la secuencia inversa puede realizarse geométricamente cortando un vértice de grado tres de un poliedro. Una transformación ΔY en la secuencia inversa puede realizarse geométricamente eliminando una cara triangular de un poliedro y extendiendo sus caras vecinas hasta el punto donde se encuentran, pero sólo cuando ese punto de intersección triple de las tres caras vecinas está en el lado más alejado de la cara eliminada del poliedro. Cuando el punto de triple intersección no está en el lado lejano de esta cara, basta una transformación proyectiva del poliedro para moverlo al lado correcto. Por tanto, por inducción sobre el número de transformaciones ΔY- e YΔ necesarias para reducir un grafo dado a , todo grafo poliédrico puede realizarse como un poliedro.
Un trabajo posterior de Epifanov reforzó la prueba de Steinitz de que todo grafo poliédrico puede reducirse a mediante transformaciones ΔY- e YΔ. Epifanov demostró que si se especifican dos vértices en un grafo plano, entonces el grafo puede reducirse a una sola arista entre esos terminales combinando transformaciones ΔY- e YΔ con reducciones serie-paralelo. La prueba de Epifanov era complicada y no constructiva, pero fue simplificada por Truemper usando métodos basados en menores de grafos. Truemper observó que todo grafo reticular es reducible mediante transformaciones ΔY- e YΔ de este modo, que esta reducibilidad se conserva mediante menores de grafos, y que todo grafo plano es un menor de un grafo reticular. Esta idea puede utilizarse para sustituir el lema de Steinitz de que existe una secuencia de reducción. Después de esta sustitución, el resto de la demostración se puede llevar a cabo utilizando la inducción de la misma manera que la demostración original de Steinitz. Para estas demostraciones, llevadas a cabo utilizando cualquiera de las formas de encontrar secuencias de ΔY- e YΔ-transformaciones, existen grafos poliédricos que requieren un número no lineal de pasos. Más concretamente, todo grafo plano puede reducirse utilizando un número de pasos como máximo proporcional a , e infinitas gráficas requieren un número de pasos al menos proporcional a , donde es el número de vértices del grafo.
Una forma alternativa de prueba por inducción se basa en eliminar aristas (y comprimir los vértices de grado dos que puedan quedar tras esta eliminación) o contraer aristas y formar un menor del grafo plano dado. Cualquier grafo poliédrico puede reducirse a por un número lineal de estas operaciones, y de nuevo las operaciones pueden invertirse y las operaciones invertidas realizarse geométricamente, dando una realización poliédrica del grafo. Sin embargo, aunque es más sencillo demostrar que existe una secuencia de reducción para este tipo de argumento, y las secuencias de reducción son más cortas, los pasos geométricos necesarios para invertir la secuencia son más complicados.
Elevación Si se dibuja un gráfico en el plano con aristas rectilíneas, se define una tensión de equilibrio como una asignación de números reales distintos de cero
(pesos) a las aristas, con la propiedad de que cada vértice está en la posición dada por la media ponderada de sus vecinos. Según la correspondencia Maxwell-Cremona, una tensión de equilibrio puede elevarse a una superficie tridimensional continua lineal a trozos tal que las aristas que forman los límites entre las partes planas de la superficie se proyecten al dibujo dado. El peso y la longitud de cada arista determinan la diferencia de pendientes de la superficie a ambos lados de la arista, y la condición de que cada vértice esté en equilibrio con sus vecinos equivale a la condición de que estas diferencias de pendientes hagan que la superficie se encuentre consigo misma correctamente en la vecindad del vértice. Los pesos positivos se traducen en ángulos diedros convexos entre dos caras de la superficie lineal a trozos, y los pesos negativos se traducen en ángulos diedros cóncavos. A la inversa, toda superficie lineal a trozos continua procede de una tensión de equilibrio de este modo. Si se dibuja un grafo plano finito y se le da una tensión de equilibrio de tal forma que todas las aristas interiores del dibujo tengan pesos positivos, y todas las aristas exteriores tengan pesos negativos, al trasladar esta tensión a una superficie tridimensional de esta forma, y luego sustituir la superficie plana que representa el exterior del grafo por su complemento en el mismo plano, se obtiene un poliedro convexo, con la propiedad adicional de que su proyección perpendicular sobre el plano no tiene cruces.