Balinski's theorem
{{short description|Graphs of d-dimensional polytopes are d-connected}}
In polyhedral combinatorics, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of three-dimensional convex polyhedra and higher-dimensional convex polytopes. It states that, if one forms an undirected graph from the vertices and edges of a convex d-dimensional convex polyhedron or polytope (its skeleton), then the resulting graph is at least d-vertex-connected: the removal of any d − 1 vertices leaves a connected subgraph. For instance, for a three-dimensional polyhedron, even if two of its vertices (together with their incident edges) are removed, for any pair of vertices there will still exist a path of vertices and edges connecting the pair.{{citation|first=Günter M.|last=Ziegler|authorlink=Günter M. Ziegler|title=Lectures on Polytopes|publisher=Springer-Verlag|orig-year=1995|series=Graduate Texts in Mathematics|volume=152|contribution=§3.5: Balinski's Theorem: The Graph is d-Connected |contribution-url={{GBurl|xd25TXSSUcgC|p=95}} |page=95– |isbn=978-0-387-94365-7 |year=2007}}.
Balinski's theorem is named after mathematician Michel Balinski, who published its proof in 1961,{{citation|title=On the graph structure of convex polyhedra in n-space|first=M. L.|last=Balinski|authorlink=Michel Balinski|journal=Pacific Journal of Mathematics|volume=11|issue=2|year=1961|pages=431–434|mr=0126765|url=http://projecteuclid.org/euclid.pjm/1103037323|doi=10.2140/pjm.1961.11.431|doi-access=free}}. although the three-dimensional case dates back to the earlier part of the 20th century and the discovery of Steinitz's theorem that the graphs of three-dimensional polyhedra are exactly the three-connected planar graphs.{{citation|first=E.|last=Steinitz|authorlink=Ernst Steinitz|contribution=Polyeder und Raumeinteilungen|title=Encyclopädie der mathematischen Wissenschaften, Band 3 (Geometries)|year=1922|pages=1–139}}.
Balinski's proof
Balinski proves the result based on the correctness of the simplex method for finding the minimum or maximum of a linear function on a convex polytope (the linear programming problem). The simplex method starts at an arbitrary vertex of the polytope and repeatedly moves towards an adjacent vertex that improves the function value; when no improvement can be made, the optimal function value has been reached.
If S is a set of fewer than d vertices to be removed from the graph of the polytope, Balinski adds one more vertex v0 to S and finds a linear function ƒ that has the value zero on the augmented set but is not identically zero on the whole space. Then, any remaining vertex at which ƒ is non-negative (including v0) can be connected by simplex steps to the vertex with the maximum value of ƒ, while any remaining vertex at which ƒ is non-positive (again including v0) can be similarly connected to the vertex with the minimum value of ƒ. Therefore, the entire remaining graph is connected.