AFTD Auto-Formalizing Theoretical Domains

in_m_leafy_trees

def

LT_n^m is the set of m-leafy trees with n internal vertices and mn + 1 leaves.

Statement

def in_m_leafy_trees (m n : ℕ) (t : PlaneTree) : Prop
Defined in
arXiv:2611.10154 Sec. 2.2
Verified
10 Nov 2026
Axioms
none listed
Built on 4
  • PlaneTreeA finite plane tree is either a leaf or an internal node with a list of child plane trees.
  • plane_tree_num_leavesThe number of leaves of a plane tree T, denoted ℓ(T).
  • is_m_leafyA tree T is m-leafy if every rooted subtree T_v satisfies ℓ(T_v) > m * n(T_v).
  • plane_tree_num_internalThe number of internal vertices of a plane tree T, denoted n(T).
Used by 6

Read back from the Lean

in_m_leafy_trees m n t defines the proposition that a plane tree t satisfies three conditions: 1. t is m-leafy, meaning that every subtree s of t satisfies m * (number of internal nodes of s) < (number of leaves of s). 2. The number of internal nodes of t is equal to n. 3. The number of leaves of t is equal to m * n + 1.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Membership in LT_n^m: m-leafy trees with n internal vertices and mn + 1 leaves. -/
def in_m_leafy_trees (m n : ℕ) (t : PlaneTree) : Prop := is_m_leafy m t ∧ plane_tree_num_internal t = n ∧ plane_tree_num_leaves t = m * n + 1
See it in the graphDiscuss this resultChallenge it