Teorema de Balinski
Afirma que, si uno forma un grafo no dirigido desde los vértices y aristas de un poliedro d-tridimensional convexo o politopo (su esqueleto), entonces la gráfica resultante es al menos d-vértices conectados: la eliminación de cualquier d - 1 vértices deja un subgrafo conexo.
[1] El teorema de Balinski se llama así por el matemático Michel Balinski, quien publicó su demostración en 1961,[2] aunque el caso tridimensional se remonta a la primera parte del siglo XX y el descubrimiento del teorema de Steinitz que las gráficas de poliedros tridimensionales son exactamente los tres grafos planos conectados.
[3] 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 repetidas ocasiones 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 de la función óptima.
Entonces, cualquier vértice restante a la que ƒ no es negativo (incluyendo v0) puede ser conectado por pasos simplex al vértice con el máximo valor de ƒ, mientras que cualquier vértice restante a la que ƒ no es positivo (de nuevo incluyendo v0) puede ser conectado de manera similar al vértice con el valor mínimo de ƒ.
