Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 5.11 — every tree on n ≥ 2 vertices has at least two leaves

Proved
AppliedComb.Graphs.tree_two_leaves

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgraph-theoryp2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1trees

Let T=(V,E)T = (V, E)T=(V,E) be a tree (a connected graph containing no cycle) on n=∣V∣n = |V|n=∣V∣ vertices, and call a vertex vvv a leaf if deg⁡T(v)=1\deg_T(v) = 1degT​(v)=1. If n≥2n \ge 2n≥2, then

∣{v∈V:deg⁡T(v)=1}∣≥2.\bigl|\{v \in V : \deg_T(v) = 1\}\bigr| \ge 2.​{v∈V:degT​(v)=1}​≥2.

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 VVV be a finite type of vertices, and let GGG be a simple graph on VVV whose adjacency relation is decidable. Let nnn be a natural number. The theorem assumes three things:

  • ∣V∣=n|V| = n∣V∣=n;
  • n≥2n \ge 2n≥2;
  • GGG is a tree. Here that means GGG is connected (VVV is nonempty and any two vertices are joined by a walk) and GGG is acyclic. Acyclic means there is no list (x1,…,xk)(x_1, \dots, x_k)(x1​,…,xk​) of pairwise distinct vertices with k≥3k \ge 3k≥3, xi∼Gxi+1x_i \sim_G x_{i+1}xi​∼G​xi+1​ for 1≤i<k1 \le i < k1≤i<k, and x1∼Gxkx_1 \sim_G x_kx1​∼G​xk​.

Conclusion. The set of vertices of degree exactly 111 has at least two elements:

∣{ v∈V:deg⁡G(v)=1 }∣ ≥ 2.\bigl|\{\, v \in V : \deg_G(v) = 1 \,\}\bigr| \ \ge\ 2.​{v∈V:degG​(v)=1}​ ≥ 2.

Here deg⁡G(v)\deg_G(v)degG​(v) is the number of neighbours of vvv in GGG.

Degenerate cases.

  • Role of nnn: nnn appears only as a name for ∣V∣|V|∣V∣, so the hypotheses amount to ∣V∣≥2|V| \ge 2∣V∣≥2 together with GGG 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
  • Endorsed by Shuze Chen · Oct 2, 2026

    Confirmed by the moderator at approval.

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