Eliminar dos vértices cualesquiera (amarillos) no permite desconectar los vértices restantes de un poliedro tridimensional: se puede elegir un tercer vértice (verde) y una función lineal no trivial cuyo conjunto de ceros (azul) pase por estos tres vértices, lo que permite conexiones desde el vértice elegido al mínimo y al máximo de la función, y desde cualquier otro vértice al mínimo o al máximo
En combinatoria poliédrica, una rama de las matemáticas, el teorema de Balinski es una declaración acerca de la estructura de la teoría de grafos de poliedros tridimensionales y politopos de dimensiones superiores. Afirma que, si se forma un grafo no dirigido desde los vértices y aristas de un poliedro d-tridimensional convexo o politopo (su esqueleto), entonces el grafo resultante es al menos d-vértices conectado: la eliminación de cualquier d-1 vértices deja un subgrafo conexo. Por ejemplo, para un poliedro tridimensional, incluso si dos de sus vértices (junto con sus bordes incidentes) se eliminan, para cualquier par de los vértices restantes todavía existirá un camino de vértices y aristas que conectan el par.
El teorema de Balinski se llama así por el matemático Michel Balinski, quien publicó su demostración en 1961, aunque el caso tridimensional se remonta a la primera parte del sigloXX y al descubrimiento del teorema de Steinitz, que afirma que los grafos de los poliedros tridimensionales son exactamente tres grafos planos conectados.
Demostración de Balinski
Balinski demuestra el resultado basado en la exactitud del algoritmo símplex para encontrar el mínimo o el máximo de una función lineal en un politopo convexo (el problema de la programación lineal). El algoritmo símplex comienza en un vértice arbitrario del politopo y en sucesivas iteraciones se mueve hacia un vértice adyacente que mejora el valor de la función; cuando no hay mejoría que puede ser hecha, se ha alcanzado el valor óptimo de la función.
Si S es un conjunto de menos de d vértices que van a ser retirados del grafo del politopo, Balinski añade un vértice más v0 a S y encuentra una función lineal ƒ que tiene el valor cero en el conjunto ampliado pero no es idénticamente igual a cero en el espacio completo. Entonces, cualquier vértice restante en el que ƒ no sea negativo (incluyendo v0) puede ser conectado por pasos de un algoritmo símplex al vértice con el máximo valor de ƒ, mientras que cualquier vértice restante en el que ƒ no sea positivo (de nuevo incluyendo v0) puede ser conectado de manera similar al vértice con el valor mínimo de ƒ. Por lo tanto, todo el gráfico restante está conectado.
