# Balinski's theorem

__: Graphs of d-dimensional polytopes are d-connected__

**Short description**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.^{[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'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 *v*_{0} 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 *v*_{0}) 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 *v*_{0}) can be similarly connected to the vertex with the minimum value of ƒ. Therefore, the entire remaining graph is connected.

## References

- ↑ Ziegler, Günter M. (2007), "§3.5: Balinski's Theorem: The Graph is
*d*-Connected",*Lectures on Polytopes*, Graduate Texts in Mathematics,**152**, Springer-Verlag, p. 95–, ISBN 978-0-387-94365-7, https://books.google.com/books?id=xd25TXSSUcgC&pg=PA95. - ↑ Balinski, M. L. (1961), "On the graph structure of convex polyhedra in
*n*-space",*Pacific Journal of Mathematics***11**(2): 431–434, doi:10.2140/pjm.1961.11.431, http://projecteuclid.org/euclid.pjm/1103037323. - ↑ Steinitz, E. (1922), "Polyeder und Raumeinteilungen",
*Encyclopädie der mathematischen Wissenschaften, Band 3 (Geometries)*, pp. 1–139.

Original source: https://en.wikipedia.org/wiki/Balinski's theorem.
Read more |