Graph connectivity | Theorems in graph theory | Theorems in discrete geometry | Polyhedral combinatorics
Balinski's theorem
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. Balinski's theorem is named after mathematician Michel Balinski, who published its proof in 1961, 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. (Wikipedia).
