Proposition 5.11 — every tree on n ≥ 2 vertices has at least two leaves
ProvedAppliedComb.Graphs.tree_two_leavescombinatoricsgraph-theoryp2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1trees
Let be a tree (a connected graph containing no cycle) on vertices, and call a vertex a leaf if . If , then
This is the elementary fact behind induction on trees: removing a leaf from a tree leaves a tree.
Preamble
import Mathlib import Definitions.Def_AppliedComb_Graphs_IsCycle
Formal statement
namespace AppliedComb.Graphs
/-- Keller–Trotter, p. 74, Proposition 5.11. Every tree on `n ≥ 2` vertices has at least two
leaves, a leaf being a vertex of degree `1`. -/
theorem tree_two_leaves {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj]
(n : ℕ) (hn : Fintype.card V = n) (h2 : 2 ≤ n) (hT : IsTree G) :
2 ≤ (Finset.univ.filter (fun v : V => G.degree v = 1)).card := by sorry
end AppliedComb.Graphs
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 74, Proposition 5.11
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let be a finite type of vertices, and let be a simple graph on whose adjacency relation is decidable. Let be a natural number. The theorem assumes three things:
- ;
- ;
- is a tree. Here that means is connected ( is nonempty and any two vertices are joined by a walk) and is acyclic. Acyclic means there is no list of pairwise distinct vertices with , for , and .
Conclusion. The set of vertices of degree exactly has at least two elements:
Here is the number of neighbours of in .
Degenerate cases.
- Role of : appears only as a name for , so the hypotheses amount to together with being a tree.
- Fewer than 2 vertices: graphs on 0 or 1 vertices are excluded by the hypotheses, and the theorem says nothing about them.
- Exactly 2 vertices: the only tree is the single edge, whose two endpoints both have degree 1.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.