Theorem 1 — has edge-disjoint spanning trees iff for every partition
ProvedNashWilliams61.TreePacking.theorem_1Let be a finite unoriented multigraph without loops (parallel edges allowed) on a non-empty vertex set , and let be a positive integer. For a partition of let be the set of edges whose ends lie in different members of . Then has pairwise edge-disjoint spanning trees if and only if
This is the tree-packing theorem, proved independently by Tutte (1961) and Nash-Williams (1961). It characterises the maximum number of edge-disjoint spanning trees by a min-max formula over vertex partitions and underlies the theory of matroid base packing.
Formalization Note is assumed non-empty (the paper's graphs have a vertex; on an empty vertex set no tree exists while (1) holds). The trees are a family indexed by with pairwise disjoint edge sets, each a spanning tree of in the multigraph sense. The inequality (1) is in and is required for every partition, including the one-part partition and the partition into singletons.
import Mathlib import Definitions.Def_NagamochiIbaraki_EdgeConn_Multigraph import Definitions.Def_NashWilliams61_TreePacking_Graphs open NagamochiIbaraki.EdgeConn
namespace NashWilliams61.TreePacking
/-- **Theorem 1** (Nash-Williams 1961, p. 445). A finite loopless multigraph `G` on a
non-empty vertex set has `k` edge-disjoint spanning trees if and only if
`|E_P(G)| ≥ k(|P| − 1)` for every partition `P` of `V(G)`. -/
theorem theorem_1 {V E : Type} [Fintype V] [DecidableEq V] [Nonempty V] [Fintype E]
[DecidableEq E] (ends : E → Sym2 V) (hloop : ∀ e, ¬ (ends e).IsDiag) (k : ℕ) (hk : 0 < k) :
(∃ T : Fin k → Finset E, (∀ i j, i ≠ j → Disjoint (T i) (T j)) ∧
∀ i, IsSpanningTree ends (T i)) ↔
∀ P : Finpartition (Finset.univ : Finset V),
(k : ℤ) * ((P.parts.card : ℤ) - 1) ≤ ((crossing ends P).card : ℤ) := by sorry
end NashWilliams61.TreePacking
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.