AFTD Auto-Formalizing Theoretical Domains

is_graceful_tree

def

A 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₁} and {u₂, v₂} of G, if the edge differences |f(u₁) - f(v₁)| and |f(u₂) - f(v₂)| are equal, then {u₁, v₁} = {u₂, v₂}.

Statement

def is_graceful_tree {W : Type*} [Fintype W] (G : SimpleGraph W) : Prop
Defined in
arXiv:2611.01340 Section 1; Golomb 1972
Verified
07 Nov 2026
Axioms
none listed
Used by 2
  • graceful_supertree_sizeFor 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 +…
  • is_graceful_tree_star_twoThe two-vertex star tree on Fin 2 is a graceful tree.

Read back from the Lean

For a finite type W and a simple graph G on W, is_graceful_tree G asserts that: 1. G is a tree (G.IsTree, meaning connected and acyclic). 2. There exists a bijection f : W ≃ Fin (Fintype.card W) such that for all vertices u₁, v₁, u₂, v₂ : W, if u₁ is adjacent to v₁ in G and u₂ is adjacent to v₂ in G, and Nat.dist (f u₁) (f v₁) = Nat.dist (f u₂) (f v₂) (the absolute difference between f u₁ and f v₁ as natural numbers equals the absolute difference between f u₂ and f v₂), then the unordered pair s(u₁, v₁) equals s(u₂, v₂) in Sym2 W (i.e., {u₁, v₁} = {u₂, v₂}).

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

/-- A tree G on a finite vertex type is graceful if there exists a bijection f from its vertices to {0, ..., |W|-1} such that the edge differences |f(u) - f(v)| are pairwise distinct for all edges of G. -/
def is_graceful_tree {W : Type*} [Fintype W] (G : SimpleGraph W) : Prop := G.IsTree ∧ ∃ f : W ≃ Fin (Fintype.card W),
    ∀ ⦃u₁ v₁ u₂ v₂ : W⦄, G.Adj u₁ v₁ → G.Adj u₂ v₂ →
      Nat.dist (f u₁) (f v₁) = Nat.dist (f u₂) (f v₂) → s(u₁, v₁) = s(u₂, v₂)
See it in the graphDiscuss this resultChallenge it