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 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 20^th century and the discovery of Steinitz's theorem that the graphs of three-dimensional polyhedra are exactly the three-connected planar graphs. 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 ƒ.

For Balinski's theorem, the abstraction is narrower than the article's general subject matter: a positive case must preserve 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. Retaining only the name, a familiar example, or a downstream effect is insufficient. The specialist roles and tests remain anchored in polyhedral combinatorics, which is why this identity is domain-specific rather than prime.

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.

Structural Signature¶

Sig role-phrases:

Defining carrier — 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 ƒ.
Constitutive relation — 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).
Operating condition — 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.
Recognition evidence — 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.
Admissible variation — Therefore, the entire remaining graph is connected.
Characteristic consequence — 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.
Failure boundary — 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.

What It Is Not¶

Not the whole field of polyhedral combinatorics. The node requires the specific identity stated by 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.
Not an over-broad reading. 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.
Not an over-broad reading. 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).
Not an over-broad reading. 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.
Not automatically Integer points in convex polyhedra. Retrieval proximity does not establish equivalence; the two identities must be compared by carrier, operation, and failure boundary.

Scope of Application¶

Balinski's theorem applies literally inside polyhedral combinatorics wherever the source-defined carrier and relation can be established. Its documented habitats include:

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 function value has been reached.
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 linear function ƒ that has the value zero on the augmented set but is not identically zero on the whole space.
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 at which ƒ is non-positive (again including v 0 ) can be similarly connected to the vertex with the minimum value of ƒ.
Balinski's proof. Therefore, the entire remaining graph is connected.
Documented setting. 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.

Outside polyhedral combinatorics, the name should be retained only when these same operational conditions survive; otherwise the comparison belongs to the broader parent Pattern or should be marked as analogy.

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. The strongest recognition evidence in the frozen account is: 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. A report should distinguish that evidence from a proxy, consequence, or common implementation. It should also state the qualification 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. so that a reader can reproduce the classification rather than infer it from topical resemblance.

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 three-dimensional convex polyhedra and higher-dimensional convex polytopes. This compression makes cases comparable while leaving parameters, conventions, exceptions, and evidential quality explicit. It is lossy by design: local history and implementation details may be omitted only when they do not alter the defining relation.

Abstract Reasoning¶

Type the carrier. Identify the polyhedral combinatorics entities to which the claim applies.
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.
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.
Demand recognition evidence. 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.
Test variation. Change an implementation or setting while preserving therefore, the entire remaining graph is connected.
Run the collapse test. Remove the defining operation; if the label still seems equally apt, only a topic or correlate was retained.
Reduce cautiously. When the specialist conditions cannot be carried, route the residual comparison to Pattern.

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 improvement can be made, the optimal function value has been reached.

Beyond the home domain. No canonical parent is asserted for Balinski's theorem. An outside case receives the specialist name only when the same typed roles and rejection conditions can be filled literally; otherwise the comparison remains an analogy pending later graph densification.

Examples¶

Canonical¶

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 ƒ. This case is canonical because it supplies a concrete carrier and lets the defining relation be checked rather than merely named.

Mapped back: carrier → the entities in the documented case; operation → 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; recognition evidence → 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

Applied / In Practice¶

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 20^th century and the discovery of Steinitz's theorem that the graphs of three-dimensional polyhedra are exactly the three-connected planar graphs. The applied case shows how the identity is used under a second setting or qualification while keeping the same operative relation.

Mapped back: changed setting → the applied context; invariant → 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; boundary → the case exits the class when 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

Structural Tensions¶

T1 — Stable identity versus admissible variation. 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. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Which changes preserve the defining relation, and which replace it?

T2 — Recognition versus proxy. 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 tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the cited evidence establish the identity or only a correlated sign?

T3 — Definition versus implementation. 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. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Is the observed implementation constitutive, optional, or merely common?

T4 — Scope versus overextension. 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 ƒ. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Can every claimed application fill the same typed roles without metaphor?

T5 — Transfer versus domain accent. 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 ƒ. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the receiving case instantiate Balinski's theorem literally, co-instantiate Pattern, or only resemble it?

T6 — Autonomy versus reduction. 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 tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: What does Balinski's theorem distinguish that the broader parent Pattern leaves together?

Structural–Framed Character¶

Balinski's theorem is mixed or framed-leaning. Its structural side is the repeatable organization summarized by 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. Its framed side is the polyhedral combinatorics vocabulary that fixes the carrier, evidence, exceptions, and admissible transformations.

Evaluative weight: the identity can be stated descriptively even when applications carry practical stakes. Human-practice dependence: the source-grounded carrier determines whether the relation exists independently or is constituted by a practice. Institutional origin: disciplinary conventions stabilize the name and test. Vocabulary portability: 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. Import versus recognition: literal transfer requires the same mechanism; shape alone is analogy.

Its portable skeleton is Pattern. Its character: a recurring specialist identity whose thin organization can be abstracted, while its operational meaning remains domain-bound.

Structural Core vs. Domain Accent¶

What is skeletal. 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. The stable skeleton is the typed relation expressed in that definition and the entry's recognition and collapse tests. The source identifies these operative conditions: 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 ƒ. 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). It further constrains recognition and variation through: 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.

What is domain-bound. polyhedral combinatorics supplies the operative entities, technical vocabulary, warrants, and exceptions that make Balinski's theorem literal. Its documented scope includes the condition that 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). Another bounded application condition is that 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. These are not decorative examples; they determine which carrier and evidence can fill the abstraction's roles.

Why no parent is asserted. Removing those specialist details does not currently yield one live catalog node that is a necessary genus for every instance. The entry is therefore approved as unparented rather than attached by topical resemblance. Its collapse evidence remains specific—Therefore, the entire remaining graph is connected.—and future graph densification may discover a defensible relation only if it preserves that boundary.

Approved unparented node. No current live node supplies a defensible necessary genus or structural prerequisite for Balinski's theorem. The reviewed identity 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. The accelerated suggestion was declined because topical or lexical similarity does not establish hierarchy; the node is admitted without a parent pending later graph densification.
Related reasoning operations. Evidence, representation, comparison, classification, transformation, or evaluation may participate in particular cases, but participation does not make any one of them a necessary parent of every instance.

Neighborhood in Abstraction Space¶

Balinski's theorem sits in a sparse region of the domain-specific corpus (60^th 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

Constrained optimization — 0.87
Conic Optimization — 0.86
Self-concordant function — 0.85
Integer points in convex polyhedra — 0.84
Biconvex optimization — 0.84

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

Not to Be Confused With¶

Pattern. The parent omits the specialist differentia. Tell: Can the case establish 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?
Integer points in convex polyhedra. The study of integer points in convex polyhedra is motivated by questions such as "how many nonnegative integer-valued solutions does a system of linear equations with nonnegative coefficients have" or "how many solutions does an integer linear program have". Tell: Which entry's carrier, operation, and failure condition are satisfied?
0/1-polytope. A convex polytope whose vertices are selected binary vectors from a finite-dimensional hypercube. Tell: Which entry's carrier, operation, and failure condition are satisfied?
Planarity. The graph property of admitting a crossing-free drawing in the plane — pinned by Kuratowski/Wagner to a finite obstruction (no K₅ or K₃,₃) and by Euler's formula to a density bound, which is why a shelf of NP-hard problems turns polynomial on planar graphs. Tell: Which entry's carrier, operation, and failure condition are satisfied?
A measurement, proxy, or consequence. Those may provide evidence without being the identity. Tell: Would Balinski's theorem remain present if the detector or downstream effect changed?
A metaphorical analogue. A similar shape outside polyhedral combinatorics lacks the specialist mechanism. Tell: Do the native roles transfer literally, or only the parent Pattern?

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Balinski%27s_theorem (revision 1292492848).
Preserved source candidate: http://projecteuclid.org/euclid.pjm/1103037323

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.