Balinski's theorem

Balinski's theorem states that the graph of every convex polytope of dimension d is d-vertex-connected: deleting fewer than d vertices leaves it connected.

Connect

Convex polytope: A bounded intersection of finitely many half-spaces in a finite-dimensional real vector space. The theorem applies to the graphs formed by these geometric objects.
Facet: A face of a polytope whose dimension is one less than the polytope's dimension. Facets let the proof reduce connectivity questions to lower-dimensional faces.
Michel Balinski: A mathematician known for work in mathematical economics, optimization, and discrete mathematics. He proved the polytope connectivity theorem that bears his name.
Simple polytope: A d-dimensional polytope in which exactly d edges meet at each vertex. Its graph has degree d at every vertex, matching the theorem's connectivity lower bound.
Polytope graph: The graph whose vertices and edges are the vertices and edges of a polytope. Balinski's theorem asserts a connectivity property of this graph.
Face lattice: The partially ordered set of a polytope's faces, ordered by inclusion. Its nested faces organize the inductive structure behind the proof.
Linear programming: Optimization of a linear objective subject to linear equality and inequality constraints. Polytope graphs encode adjacency among feasible solutions in linear programming.
Hirsch conjecture: A conjecture that every d-dimensional polytope with n facets has graph diameter at most n minus d. It concerns distances in the same graphs whose connectivity Balinski established.
Vertex connectivity: The minimum number of vertices whose deletion disconnects a graph or reduces it to a trivial graph. The theorem gives a lower bound on this graph invariant.
Induction: A proof method establishing a base case and deriving each case from smaller ones. The standard proof uses dimension induction to establish connectivity.