Balinski's theorem
Encyclopedia
In polyhedral combinatorics
, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic
structure of three-dimensional polyhedra
and higher-dimensional polytope
s. It states that, if one forms an undirected graph from the vertices and edges of a convex d-dimensional 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 L. 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.
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.
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....
, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
structure of three-dimensional polyhedra
Polyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
and higher-dimensional polytope
Polytope
In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...
s. It states that, if one forms an undirected graph from the vertices and edges of a convex d-dimensional polyhedron or polytope (its skeleton), then the resulting graph is at least d-vertex-connected
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
: 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 L. 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
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 for finding the minimum or maximum of a linear function on a convex polytope (the linear programmingLinear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
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.