Lemma 2 — every connected graph has a spanning tree
ProvedNashWilliams61.TreePacking.lemma_2graph-theorymultigraphp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1spanning-tree
Let be a finite multigraph without loops and a subgraph of (every edge of has both ends in ) that is connected: is non-empty and any two vertices of are joined by a path of -edges. Then there is such that is a tree, i.e. is a spanning tree of .
Together with Lemma 1 this gives the proof of necessity of Theorem 1.
Formalization Note "Connected" is spelled out as non-empty plus pairwise reachability by -edges; the conclusion is the multigraph spanning-tree notion of the definition file.
Preamble
import Mathlib import Definitions.Def_NagamochiIbaraki_EdgeConn_Multigraph import Definitions.Def_NashWilliams61_TreePacking_Graphs open NagamochiIbaraki.EdgeConn
Formal statement
namespace NashWilliams61.TreePacking
/-- **Lemma 2** (Nash-Williams 1961, p. 445). Every connected graph has a spanning tree: if
`(W, F)` is a subgraph (every edge of `F` has both ends in `W`) with `W` non-empty and
every two vertices of `W` joined by a path of `F`-edges, then some `T ⊆ F` is a spanning
tree of `(W, F)`. -/
theorem lemma_2 {V E : Type} [DecidableEq V] [DecidableEq E] (ends : E → Sym2 V)
(hloop : ∀ e, ¬ (ends e).IsDiag) (W : Finset V) (F : Finset E)
(hF : ∀ e ∈ F, ∀ v ∈ ends e, v ∈ W) (hW : W.Nonempty)
(hconn : ∀ u ∈ W, ∀ v ∈ W, (edgeGraph ends F).Reachable u v) :
∃ T : Finset E, IsSpanningTreeOn ends W F T := by sorry
end NashWilliams61.TreePacking
Source
Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. London Math. Soc. 36 (1961), p. 445, Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.