is_graceful_tree
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₂)