Skip to content

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.

Version
v1 · 2026-09-28 · History
Domain-specific #
8108
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomain
Polyhedral Combinatorics → Mathematics

Core Idea

Balinski's theorem is treated here as the recurring polyhedral combinatorics identity summarized by this source-grounded definition: 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. 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.

How would you explain it like I'm…

The Hard-to-Break Shape Net

Think of a solid shape like a dice, with corners joined by edges. Pretend the edges are roads between the corners. Balinski's theorem says that if you knock out any two corners, you can still travel along the roads from any corner left to any other corner. For shapes in more dimensions, you can knock out even more corners and stay connected.

Hard-to-Break Corner Networks

A polytope is a flat-sided shape, like a cube or pyramid, but it can live in more than three dimensions. Its corners (vertices) and edges form a network called its graph. Balinski's theorem says that for a shape in d dimensions, you would have to remove at least d corners to break the network into separate pieces. So for a 3D shape, removing any two corners still leaves every remaining corner reachable from every other along edges. Michel Balinski published the proof in 1961.

d-Connectivity of Polytope Graphs

Balinski's theorem, from polyhedral combinatorics, is about the graph formed by the vertices and edges of a convex polytope — its skeleton. It states that for a convex d-dimensional polytope, this graph is d-vertex-connected: removing any d − 1 vertices leaves the rest connected. For a 3D convex polyhedron, removing any two vertices still leaves a path between every remaining pair. Michel Balinski published the proof in 1961; the 3D case was known earlier, as part of Steinitz's theorem that the graphs of 3D polyhedra are exactly the 3-connected planar graphs. The proof uses a linear function that is zero on the removed vertices plus one extra vertex, and connects the other vertices by moving along edges toward the function's maximum or minimum.

 

Balinski's theorem states that the vertex–edge graph (skeleton) of a d-dimensional convex polytope is d-vertex-connected: deleting any d − 1 vertices leaves a connected subgraph. In three dimensions this means any convex polyhedron's graph remains connected after removing any two vertices and their incident edges; this case predates Balinski via Steinitz's theorem, which characterizes the graphs of three-dimensional polyhedra as exactly the 3-connected planar graphs. Michel Balinski published the general proof in 1961. The proof takes a set S of fewer than d vertices, adds one more vertex v0, and chooses a linear function f that vanishes on the augmented set but is not identically zero. Every remaining vertex where f is non-negative, including v0, can be joined by simplex-style edge steps, monotone in f, to the vertex maximizing f, and every remaining vertex where f is non-positive, again including v0, can be joined to the vertex minimizing f. Since v0 lies in both groups, all remaining vertices are connected. The theorem concerns this connectivity property of polytope graphs specifically, not polyhedral combinatorics in general.

Scope of Application

  • 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).

  • Balinski's proof. 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.

  • Balinski's proof. 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.

  • Balinski's proof. 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.

  • Balinski's proof. Therefore, the entire remaining graph is connected.

Clarity

A clear use of Balinski's theorem names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is 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.

Manages Complexity

Balinski's theorem compresses multiple polyhedral combinatorics details into a stable diagnostic relation. The source shows both the central mechanism—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).—and the practical consequence—in polyhedral combinatorics, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of.

Abstract Reasoning

  1. Type the carrier. Identify the polyhedral combinatorics entities to which the claim applies.
  2. State the relation. Use the source-grounded identity: 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.
  3. Check operation and conditions. 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. 4.

Knowledge Transfer

Within the home domain. Knowledge about Balinski's theorem transfers literally when a new case preserves the same carrier type, relation, and recognition test. 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.

Neighborhood in Abstraction Space

Balinski's theorem sits in a sparse region of the domain-specific corpus (60th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Convex Optimization & Iterative Methods (8 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08