AFTD Auto-Formalizing Theoretical Domains

graceful_supertree_size

def

For a finite simple graph T, the graceful supertree size of T is the minimum number of edges M of a graceful tree on vertex set Fin (M + 1) containing T as an induced subgraph (or 0 if no such graceful tree exists).

Statement

noncomputable def graceful_supertree_size {V : Type*} [Fintype V] (T : SimpleGraph V) : ℕ
Defined in
arXiv:2611.01340 Section 1
Verified
07 Nov 2026
Axioms
none listed
Built on 1
  • is_graceful_treeA tree G on a finite vertex type W is graceful if there exists a bijection f : W ≃ Fin (Fintype.card W) such that for all edges {u₁, v₁}…

Read back from the Lean

Given a finite type V and a simple graph T on V, graceful_supertree_size T is defined as the infimum (in ℕ) of the set of natural numbers M such that there exists a simple graph G on the vertex set Fin (M + 1) satisfying: 1. G is a graceful tree (it is a tree, and there exists a bijection f from Fin (M + 1) to Fin (M + 1) such that for all vertices u₁, v₁, u₂, v₂, if {u₁, v₁} and {u₂, v₂} are edges in G and |f(u₁) - f(v₁)| = |f(u₂) - f(v₂)|, then the undirected edges s(u₁, v₁) and s(u₂, v₂) are equal); 2. There exists an embedding of simple graphs from T into G (an injective vertex map preserving and reflecting adjacency).

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

/-- The minimum number of edges s(T) of a graceful tree containing T as a subtree. -/
noncomputable def graceful_supertree_size {V : Type*} [Fintype V] (T : SimpleGraph V) : ℕ := sInf {M : ℕ | ∃ G : SimpleGraph (Fin (M + 1)),
    is_graceful_tree G ∧ Nonempty (SimpleGraph.Embedding T G)}
See it in the graphDiscuss this resultChallenge it