Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 12.4 — the exchange principle for spanning trees

Proved
AppliedComb.GraphAlg.exchange_principle

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgraph-theoryp2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1spanning-trees

Let T=(V,S)T = (V, S)T=(V,S) be a spanning tree of a finite graph GGG and let e=xye = xye=xy be an edge of GGG that is not an edge of TTT. Then:

  1. there is a unique path P=(x0,x1,…,xt)P = (x_0, x_1, \dots, x_t)P=(x0​,x1​,…,xt​) in TTT with x0=xx_0 = xx0​=x, xt=yx_t = yxt​=y and xixi+1∈Sx_i x_{i+1} \in Sxi​xi+1​∈S for i=0,…,t−1i = 0, \dots, t-1i=0,…,t−1;
  2. for each i=0,1,…,t−1i = 0, 1, \dots, t - 1i=0,1,…,t−1, with fi=xixi+1f_i = x_i x_{i+1}fi​=xi​xi+1​, the graph Ti=(V,Si)T_i = (V, S_i)Ti​=(V,Si​), where
Si={e}∪{g∈S:g≠fi},S_i = \{e\} \cup \{g \in S : g \ne f_i\},Si​={e}∪{g∈S:g=fi​},

is a spanning tree of GGG.

Exchanging one tree edge on the path for the non-tree edge eee is the step used to compare spanning trees of different weights (Lemma 12.6).

Formalization Note. A path is a Mathlib walk P : T.Walk x y with P.IsPath (distinct vertices); ttt is P.length and xix_ixi​ is P.getVert i. Part 1 is ∃! P, P.IsPath. In part 2 the statement is made for every path from xxx to yyy in TTT (by part 1 there is exactly one), and TiT_iTi​ is SimpleGraph.fromEdgeSet of the edge set {e}∪{g∈S:g≠fi}\{e\} \cup \{g \in S : g \ne f_i\}{e}∪{g∈S:g=fi​}.

Preamble
import Mathlib
import Definitions.Def_AppliedComb_GraphAlg_SpanningTree
Formal statement
namespace AppliedComb.GraphAlg

/-- Keller–Trotter, p. 241, Proposition 12.4 (Exchange Principle). Let `T = (V, S)` be a spanning
tree in a graph `G` and `e = xy` an edge of `G` not in `T`. Then (1) there is a unique path
`P = (x₀, …, x_t)` in `T` from `x = x₀` to `y = x_t`, and (2) for each `i = 0, …, t − 1`, with
`fᵢ = xᵢxᵢ₊₁`, the graph `Tᵢ = (V, Sᵢ)` with `Sᵢ = {e} ∪ {g ∈ S : g ≠ fᵢ}` is a spanning tree of
`G`. Paths are Mathlib walks with distinct vertices; `t` is the walk's length and `xᵢ` its
`i`-th vertex. -/
theorem exchange_principle {V : Type*} [Fintype V] (G T : SimpleGraph V)
    (hT : IsSpanningTree G T) (x y : V) (he : G.Adj x y) (heT : ¬ T.Adj x y) :
    (∃! P : T.Walk x y, P.IsPath) ∧
      ∀ P : T.Walk x y, P.IsPath → ∀ i : ℕ, i < P.length →
        IsSpanningTree G (SimpleGraph.fromEdgeSet
          (insert s(x, y) {g ∈ T.edgeSet | g ≠ s(P.getVert i, P.getVert (i + 1))})) := by sorry

end AppliedComb.GraphAlg
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 241, Proposition 12.4 (Exchange Principle)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setup:

  • VVV is a finite vertex type, and GGG and TTT are simple graphs on VVV.
  • TTT is a spanning tree of GGG: every edge of TTT is an edge of GGG, and TTT is connected (with VVV nonempty) and acyclic.
  • xxx and yyy are vertices such that xyxyxy is an edge of GGG but not an edge of TTT.

The theorem asserts both of the following.

  1. There is exactly one path in TTT from xxx to yyy. Here a path is a walk along edges of TTT, x=x0,x1,…,xt=yx = x_0, x_1, \dots, x_t = yx=x0​,x1​,…,xt​=y, with no repeated vertex.
  2. Let P=(x0,…,xt)P = (x_0,\dots,x_t)P=(x0​,…,xt​) be any path in TTT from xxx to yyy, and let iii be any natural number with i<ti < ti<t, where ttt is the number of edges of PPP. Define the graph TiT_iTi​ on VVV by its edge set
E(Ti)  =  {xy} ∪ {g∈E(T):g≠{xi,xi+1}}.E(T_i) \;=\; \{xy\} \,\cup\, \bigl\{ g \in E(T) : g \ne \{x_i, x_{i+1}\} \bigr\}.E(Ti​)={xy}∪{g∈E(T):g={xi​,xi+1​}}.

This set contains no loop, so it is the edge set exactly as written. Then TiT_iTi​ is a spanning tree of GGG.

Degenerate cases.

  • Because xyxyxy is an edge of GGG and GGG has no loops, x≠yx \ne yx=y. So the hypotheses force ∣V∣≥2|V| \ge 2∣V∣≥2 and t≥1t \ge 1t≥1.
  • If GGG has no edge outside TTT, no pair x,yx, yx,y satisfies the hypotheses, and the statement is vacuous.
  • Finiteness of VVV is assumed but does not appear in the conclusion.
Human review
  • Endorsed by Shuze Chen · Oct 2, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 2, 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