Proof of Theorem 4.2, p. 3:14 — a rooted subtree with between N+1 and 2N leaves
ProvedTwinWidthI.BoolWidth.exists_subtree_leaves_betweenLet be a rooted binary tree with labelled leaves (every internal node has exactly two children), and let be an integer. If has more than leaves, then there is an edge of such that the rooted subtree below satisfies
In the proof of Theorem 4.2 (with ) this is the subtree found by walking down from the root into the larger child while the current subtree has more than leaves; the edge it hangs from gives the cut with .
Formalization Note. Leaves are counted with multiplicity (the length of the leaf list), which for a decomposition tree is the number of vertices of . The edges of are its proper rooted subtrees (properSubtrees), so "below an edge" excludes the whole tree. The hypothesis is needed: every tree has at least one leaf, and the conclusion is impossible for .
import Mathlib import Definitions.Def_TwinWidthI_BoolWidth_Setting
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.