Balinski's theorem

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.

[1] Balinski's theorem is named after mathematician Michel Balinski, who published its proof in 1961,[2] 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.

[3] 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.

Removing any two vertices (yellow) cannot disconnect a three-dimensional polyhedron: one can choose a third vertex (green), and a nontrivial linear function whose zero set (blue) passes through these three vertices, allowing connections from the chosen vertex to the minimum and maximum of the function, and from any other vertex to the minimum or maximum.