Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — a tree on WWW has ∣W∣−1|W| - 1∣W∣−1 edges

Proved
NashWilliams61.TreePacking.lemma_1

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-theorymultigraphp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1spanning-tree

Let GGG be a finite multigraph without loops, and let (W,T)(W, T)(W,T) be a tree in GGG: WWW is a non-empty vertex set, every edge of TTT has both ends in WWW, TTT has no cycle, and any two vertices of WWW are joined by a path of TTT-edges. Then

∣T∣=∣W∣−1.|T| = |W| - 1 .∣T∣=∣W∣−1.

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 ∣T∣+1=∣W∣|T| + 1 = |W|∣T∣+1=∣W∣ 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
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

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