polyhedral combinatorics Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes. Research in polyhedral c ...

, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of three-dimensional

convex polyhedra A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wor ...

and higher-dimensional convex polytopes. It states that, if one forms an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

from the vertices and edges of a convex ''d''-dimensional convex polyhedron or polytope (its

skeleton A skeleton is the structural frame that supports the body of an animal. There are several types of skeletons, including the exoskeleton, which is the stable outer shell of an organism, the endoskeleton, which forms the support structure inside ...

), 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 Michel Louis Balinski (born Michał Ludwik Baliński; October 6, 1933 – February 4, 2019) was an applied mathematician, economist, operations research analyst and political scientist. As a Polish-American, educated in the United States, he l ...

, 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 In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs ...

that the graphs of three-dimensional polyhedra are exactly the three-connected planar graphs..

Balinski's proof

Balinski proves the result based on the correctness of the

simplex method In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are no ...

for finding the minimum or maximum of a linear function on a convex polytope (the

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...

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''₀ 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''₀) 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''₀) can be similarly connected to the vertex with the minimum value of ƒ. Therefore, the entire remaining graph is connected.

References

{{reflist Polyhedral combinatorics Graph connectivity Theorems in discrete geometry Theorems in graph theory