Proposition 12.4 — the exchange principle for spanning trees
ProvedAppliedComb.GraphAlg.exchange_principleLet be a spanning tree of a finite graph and let be an edge of that is not an edge of . Then:
- there is a unique path in with , and for ;
- for each , with , the graph , where
is a spanning tree of .
Exchanging one tree edge on the path for the non-tree edge 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); is P.length and is P.getVert i. Part 1 is ∃! P, P.IsPath. In part 2 the statement is made for every path from to in (by part 1 there is exactly one), and is SimpleGraph.fromEdgeSet of the edge set .
import Mathlib import Definitions.Def_AppliedComb_GraphAlg_SpanningTree
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setup:
- is a finite vertex type, and and are simple graphs on .
- is a spanning tree of : every edge of is an edge of , and is connected (with nonempty) and acyclic.
- and are vertices such that is an edge of but not an edge of .
The theorem asserts both of the following.
- There is exactly one path in from to . Here a path is a walk along edges of , , with no repeated vertex.
- Let be any path in from to , and let be any natural number with , where is the number of edges of . Define the graph on by its edge set
This set contains no loop, so it is the edge set exactly as written. Then is a spanning tree of .
Degenerate cases.
- Because is an edge of and has no loops, . So the hypotheses force and .
- If has no edge outside , no pair satisfies the hypotheses, and the statement is vacuous.
- Finiteness of is assumed but does not appear in the conclusion.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.