Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 14.1 — bases of à are spanning trees

Proved
VanderbeiLP.Networks.spanning_tree_iff_basis

by mikedeng1 · Oct 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-programmingnetwork-flowsp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1spanning-trees

Let (N,A)(N,A)(N,A) be a connected network with mmm nodes, let rrr be a root node and let A~\tilde AA~ be the node–arc incidence matrix with the row of rrr deleted. For every set T⊆AT\subseteq AT⊆A of arcs,

the columns of A~ indexed by T form a basis  ⟺  T is a spanning tree.\text{the columns of }\tilde A\text{ indexed by }T\text{ form a basis}\iff T\text{ is a spanning tree}.the columns of A~ indexed by T form a basis⟺T is a spanning tree.

Here a basis is an invertible square submatrix, i.e. ∣T∣=m−1|T|=m-1∣T∣=m−1 linearly independent columns, and a spanning tree is an arc set that is connected on all of NNN 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 ⇒\Rightarrow⇒ basis" and leaves the converse as Exercise 14.12; both are stated.

Preamble
import Mathlib
import Definitions.Def_VanderbeiLP_Networks_Network
Formal statement
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
Source
Vanderbei, Linear Programming: Foundations and Extensions, 4th ed., Springer 2014, p. 205 (PDF 216), Theorem 14.1; standing assumption p. 202
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me