2025/11/14 by Shoham Letzter, Alexey Pokrovskiy, Letzter, Shoham +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #math.CO
paper · pdf · doi:10.48550/arxiv.2511.11331
23 pages, 6 figures
openalex publication_date 2025/11/14 · openalex created_date 2025/11/18 · openalex updated_date 2026/07/28 · arxiv created 2026/07/31 · arxiv updated 2026/08/03
An n-vertex tree T is said to be graceful if there exists a bijective labelling ϕ:V(T)→ \1,…,n\ such that the edge-differences \|ϕ(x)-ϕ(y)| : xy∈ E(T)\ are pairwise distinct. The longstanding graceful tree conjecture, posed by Rósa in the 1960s, asserts that every tree is graceful. The graceful of an n-vertex tree T, denoted gs(T), is the maximum possible number of distinct edge-differences over all bijective labellings ϕ:V(T)→ \1,…,n\. The graceful tree conjecture is therefore equivalent to the statement that gs(T)=n-1 for all n-vertex trees. We prove an asymptotic version of this conjecture by showing that for every ε>0, there exists n0 such that every tree on n>n0 vertices satisfies gs(T)\geqslant (1-ε)n. In other words, every sufficiently large tree admits an almost graceful labelling.