Lemma 1 — a tree on has edges
ProvedNashWilliams61.TreePacking.lemma_1graph-theorymultigraphp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1spanning-tree
Let be a finite multigraph without loops, and let be a tree in : is a non-empty vertex set, every edge of has both ends in , has no cycle, and any two vertices of are joined by a path of -edges. Then
This standard fact (Berge, Théorie des graphes, Ch. 16, Thm 1) is used in the proof of necessity of Theorem 1 and in the final count of the proof of sufficiency.
Formalization Note Stated as to avoid natural-number subtraction; the tree is in the multigraph sense (parallel edges form a cycle).
Preamble
import Mathlib import Definitions.Def_NagamochiIbaraki_EdgeConn_Multigraph import Definitions.Def_NashWilliams61_TreePacking_Graphs open NagamochiIbaraki.EdgeConn
Formal statement
namespace NashWilliams61.TreePacking
/-- **Lemma 1** (Nash-Williams 1961, p. 445). `|E(T)| = |V(T)| − 1` for every tree `T`:
if `(W, T)` is a tree of the loopless multigraph, then `|T| + 1 = |W|`. -/
theorem lemma_1 {V E : Type} [DecidableEq V] [DecidableEq E] (ends : E → Sym2 V)
(hloop : ∀ e, ¬ (ends e).IsDiag) (W : Finset V) (T : Finset E) (hT : IsTreeOn ends W T) :
T.card + 1 = W.card := by sorry
end NashWilliams61.TreePacking
Source
Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. London Math. Soc. 36 (1961), p. 445, Lemma 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.