Balinski's THEOREM — the graph of a bounded full-dimensional polyhedron in n-space is n-tuply connected
ProvedBalinski61.Connectivity.graph_n_tuply_connectedLet be the polyhedral convex set of system (1), with Balinski's standing assumptions:
- the only solution to is ;
- there exists a solution which satisfies .
Let be the graph whose points are the vertices of and whose lines are the edges of . Then is -tuply connected: it has at least points, and for every set of at most vertices,
This is Balinski's theorem (THEOREM, p. 432): "The vertices, considered as points, and the edges, considered as lines, of the convex polyhedral set form an -tuply connected graph ." Under the two assumptions is exactly a full-dimensional polytope in , so the theorem says that the graph of every -dimensional polytope is vertex -connected, a basic structural fact of polyhedral combinatorics.
Formalization Note is the dimension of the space and the number of inequalities. The definition of -tuply connected is the paper's own ("at least points", "dropping out or fewer points"), not "exactly " as in the first lines of the proof. Edges are the extreme segments of (Hirsch.Adj), not arbitrary pairs of vertices.
import Mathlib import Definitions.Def_Hirsch_model import Definitions.Def_Balinski61_Connectivity_Polyhedron import Definitions.Def_Balinski61_Connectivity_TuplyConnected open scoped RealInnerProductSpace
namespace Balinski61.Connectivity
theorem graph_n_tuply_connected (n m : ℕ)
(a : Fin m → EuclideanSpace ℝ (Fin n)) (b : Fin m → ℝ)
(hS : StandingAssumptions a b) :
IsNTuplyConnected (polyGraph (Hirsch.Hpoly a b)) n := by sorry
end Balinski61.Connectivity
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.