Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 4.2, p. 3:14 — a rooted subtree with between N+1 and 2N leaves

Proved
TwinWidthI.BoolWidth.exists_subtree_leaves_between

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

boolean-widthdecomposition-treep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let TTT be a rooted binary tree with labelled leaves (every internal node has exactly two children), and let N≥1N\ge 1N≥1 be an integer. If TTT has more than 2N2N2N leaves, then there is an edge eee of TTT such that the rooted subtree T′T'T′ below eee satisfies

N+1 ≤ ∣leaves(T′)∣ ≤ 2N.N+1\ \le\ |\text{leaves}(T')|\ \le\ 2N .N+1 ≤ ∣leaves(T′)∣ ≤ 2N.

In the proof of Theorem 4.2 (with N=2kN=2^kN=2k) this is the subtree found by walking down from the root into the larger child while the current subtree has more than 2k+12^{k+1}2k+1 leaves; the edge eee it hangs from gives the cut Pe=(Ae,Be)P_e=(A_e,B_e)Pe​=(Ae​,Be​) with ∣Ae∣≥2k+1|A_e|\ge 2^k+1∣Ae​∣≥2k+1.

Formalization Note. Leaves are counted with multiplicity (the length of the leaf list), which for a decomposition tree is the number of vertices of AeA_eAe​. The edges of TTT are its proper rooted subtrees (properSubtrees), so "below an edge" excludes the whole tree. The hypothesis N≥1N\ge 1N≥1 is needed: every tree has at least one leaf, and the conclusion is impossible for N=0N=0N=0.

Preamble
import Mathlib
import Definitions.Def_TwinWidthI_BoolWidth_Setting
Formal statement
namespace TwinWidthI.BoolWidth

open Finset

theorem exists_subtree_leaves_between {α : Type*} (T : DTree α) (N : ℕ) (hN : 1 ≤ N)
    (hT : 2 * N < T.leaves.length) :
    ∃ S ∈ T.properSubtrees, N + 1 ≤ S.leaves.length ∧ S.leaves.length ≤ 2 * N := by sorry

end TwinWidthI.BoolWidth
Source
Bonnet, Kim, Thomassé and Watrigant, Twin-width I: Tractable FO Model Checking, J. ACM 69(1), Article 3 (2021), p. 3:14, proof of Theorem 4.2, "we find a rooted subtree of T with at least 2^k + 1 and at most 2^{k+1} leaves"
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

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