Theorem 14.1 — bases of à are spanning trees
ProvedVanderbeiLP.Networks.spanning_tree_iff_basisLet be a connected network with nodes, let be a root node and let be the node–arc incidence matrix with the row of deleted. For every set of arcs,
Here a basis is an invertible square submatrix, i.e. linearly independent columns, and a spanning tree is an arc set that is connected on all of and acyclic when directions are ignored.
The theorem translates the algebra of the simplex method on (14.1) into the combinatorics of the network: bases are spanning trees, and pivots exchange one tree arc for another.
Formalization Note The chapter's standing assumption "The network is connected" (p. 202) is a hypothesis. The book proves the direction "spanning tree basis" and leaves the converse as Exercise 14.12; both are stated.
import Mathlib import Definitions.Def_VanderbeiLP_Networks_Network
namespace VanderbeiLP.Networks
/-- **Theorem 14.1** (Vanderbei, *Linear Programming*, 4th ed., p. 205). For a connected network
`(N, A)` with root node `r`, a square submatrix of the truncated incidence matrix `Ã` is a basis
if and only if the arcs to which its columns correspond form a spanning tree. -/
theorem spanning_tree_iff_basis {N : Type*} [Fintype N] [DecidableEq N]
(A : Finset (N × N)) (hA : IsNetwork A) (hconn : IsConnectedNetwork A)
(r : N) (T : Finset (N × N)) (hT : T ⊆ A) :
IsBasisArcs r T ↔ IsSpanningTree A T := by sorry
end VanderbeiLP.Networks
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.