On the gracesize of trees

Alexey Pokrovskiy; Ella Williams; Shoham Letzter

REVIEW 3 major objections 5 minor 1 cited by

On the gracesize of trees

T0 review · 3 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Every sufficiently large tree is almost graceful.

desk verdict The main theorem is a genuine breakthrough—every large tree has gracesize (1−o(1))n—but the proof as written has a few holes in the rainbow-matching engine that need fixing before I'd trust it. read the letter →

arxiv 2511.11331 v2 pith:UCZNU2TY submitted 2025-11-14 math.CO

Shoham Letzter , Alexey Pokrovskiy , Ella Williams This is my paper · ORCID

classification math.CO MSC 05C7805C0505C70

keywords gracefullabellinggracesizetreelabellingsconjecturedifference-colouredcompletegraphrainbowsubgraphshypergraphmatchingsasymptoticcombinatorics

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

An n-vertex tree is graceful when its vertices can be labelled 1..n so that the n−1 edge differences are all distinct. The graceful tree conjecture, posed in the 1960s, says this is always possible, and it remains open. This paper proves the next best thing: for every ε>0 and all sufficiently large n, every n-vertex tree has a labelling with at least (1−ε)n distinct edge differences — a near-graceful labelling. The proof recasts the problem as finding an almost-rainbow copy of the tree in the complete graph whose edge colours are absolute differences of the labels, then splits the tree into a few high-degree vertices plus many copies of a small forest and embeds the copies using almost-perfect rainbow matchings obtained from random hypergraphs. A reader should care because the result removes the degree restriction that limited earlier asymptotic progress and shows the remaining gap to the full conjecture is quantitative, not structural.

What carries the argument

Three pieces carry the argument. (1) The difference-coloured complete graph K_X: vertex set X, edge ij coloured |i−j|; a graceful labelling is exactly a rainbow embedding of T into K_[n]. (2) A translation to 3-uniform 3-partite hypergraphs: for disjoint vertex sets A, B and colour set C, an edge ab of colour c becomes the hyperedge {a,b,c}; rainbow matchings in K correspond to hypergraph matchings, so an almost-perfect matching theorem for linear hypergraphs yields almost-perfect rainbow matchings between random sets. (3) A tree-splitting lemma: after deleting a small set W of waste vertices, T∖(W∪S_high) decomposes into ζn disjoint copies of one small forest F, with all edges from copies i

What would settle it

Simulate Lemma 5.4 for, say, n=10⁴, p=0.1, µ=0.05 and count vertices in H_P whose degree deviates from its expectation by more than the γ factor; the theorem predicts such vertices number o(|H_P|), and a counterexample near the boundary would show the proof's matching claim is not guaranteed.

Watch

Extended reading notes

Core claim

The paper's central claim, Theorem 1.3, is that for every ε>0 there is n0 such that every n-vertex tree T with n>n0 satisfies gs(T) ≥ (1−ε)n. Equivalently, T embeds into the difference-coloured complete graph on [(1+ε)n] vertices with at least (1−ε)n distinct edge colours appearing. The authors first prove a stronger intermediate statement: even if labels are allowed to range up to (1+ε)n, the same fraction of distinct differences is achievable; a leaf-stripping argument then converts this into the gracesize estimate. The core discovery is that, for all sufficiently large trees, a near-graceful labelling exists regardless of maximum degree — the high-degree vertices are not the obstruction.

Load-bearing premise

The proof rests on the claim that the random hypergraphs built from the difference-coloured graph have almost all vertices of near-expected degree; if many vertices near the boundaries of the label interval fail this, the almost-perfect rainbow matching lemma — the core embedding tool — breaks down.

Editorial extensions

If this is right

Every sufficiently large tree has gracesize at least (1−ε)n, giving the current best universal lower bound toward the graceful tree conjecture.
Every large tree admits a labelling into [(1+ε)n] with at least (1−ε)n distinct edge differences, with no restriction on maximum degree.
The earlier (1−o(1))n bound, known for trees of maximum degree o(n/log n), now follows as a special case of a statement covering all trees.
The paper identifies a natural next target: prove that every tree has a range-relaxed graceful labelling into [(1+o(1))n], which would essentially complete the asymptotic version of the conjecture.
The constructed labelling uses at most εn repeated colours, so the proof gives a linear, arbitrarily small collision budget rather than a merely asymptotic one.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A full solution of the graceful tree conjecture would likely have to make the rainbow-matching step exact rather than approximate, since the other losses in the proof are introduced deliberately and could in principle be removed by more careful bookkeeping.
The same hypergraph-matching framework may extend to other rainbow embedding problems in difference-coloured complete graphs, such as finding almost-rainbow copies of bounded-degree spanning subgraphs besides trees.
A concrete computational check for moderate n — whether the random hypergraph in the matching lemma really has only o(n) low-degree vertices counting the boundary cases — would either validate the core step or pinpoint a repairable gap near the ends of the label interval.
Because the proof only uses that each vertex set has at most one earlier neighbour in the ordering, it may adapt to forests with bounded component size after deleting a small set, not just trees.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know two things. First, if the proof is correct, this is a major result: it resolves the asymptotic form of the graceful tree conjecture for all trees, removing the Δ=o(n/log n) barrier in Adamaszek–Allen–Grosu–Hladký. Second, as written, the proof does not quite compile in the key matching lemma, and the stress-test note is right about where.

What's new and good: the reduction from Lemma 1.4 to Theorem 1.3 is clean, and the idea of embedding an auxiliary tree via rainbow blow-up is genuinely new. The tree-splitting lemma (Lemma 4.1) is solid, and the high-level architecture—split off high-degree vertices, embed the rest by matchings, then absorb waste vertices—is sensible. The paper is written in a way that a knowledgeable reader can actually check the details, which is a credit.

The soft spots are all in Lemma 5.4. The application of Theorem 5.3 to H_P requires a bound on the number of low-degree vertices; the paper only proves concentration on the 'good' intervals and never counts the boundary vertices, which can have expected degree a constant fraction below the target. The McDiarmid argument for b∈B2 is invalid as written: flipping b itself changes d_{H_P}(b) by up to 2s, so the function is not 2-Lipschitz on the stated product space. And the final coverage count 'all but 2μ max{|S1|,|S2|}' does not follow from the per-hypergraph matching bounds, since the colour class is a clone of S2 and the total vertex count is |S1|+2|S2|. There is also a numerical error in Theorem 5.3's displayed inequality: it requires (1−γ)/(1+γ) ≥ 2, which is impossible. These are not deep conceptual failures—I expect a standard Chernoff/McDiarmid repair plus constant absorption would fix them—but the proof as printed is not complete.

Who should read this: anyone working on graceful labellings or rainbow embeddings. It deserves a serious referee, but the referee should be told to focus on Lemma 5.4 and ask for a corrected version before acceptance. I would not cite it yet; I'd wait for a revised version.

Referee Report

3 major / 5 minor

Summary. The paper proves that for every ε>0, all sufficiently large n-vertex trees T have gracesize at least (1−ε)n, i.e. T admits a bijective labelling into [n] with at least (1−ε)n distinct edge-differences. The proof embeds T almost-rainbowly into the difference-coloured complete graph K[(1+ε)n] via a three-stage argument: (i) a tree-splitting lemma (Lemma 4.1) finds a small set W and a set S_high so that T−W decomposes into many copies of a small rooted forest, with roots adjacent only to S_high; (ii) a random-hypergraph matching lemma (Lemma 5.4) supplies almost-perfect rainbow matchings between vertex parts; (iii) an auxiliary-tree construction (Lemma 5.9) uses these matchings to embed the remaining forest rainbowly. The paper improves earlier work by removing all maximum-degree restrictions.

Significance. This is a substantial advance toward the graceful tree conjecture. The main result — an asymptotically optimal gracesize bound for all trees — goes well beyond the previous degree-restricted theorem of Adamaszek–Allen–Grosu–Hladký and the constant-factor bound of Rosa–Širáň. The paper is also methodologically attractive: it shifts the problem to anti-Ramsey embeddings, uses a clean tree-splitting lemma, and provides explicit constructions for the rainbow matchings. The proof is mostly elementary and carefully parameterised. However, the core embedding lemma (Lemma 5.4) has proof gaps that, as written, prevent the central claim from being verified; these gaps are locally repairable but require substantial additional estimates.

major comments (3)

[§5.1, Claim 5.5] The verification of the hypotheses of Theorem 5.3 for H_P is incomplete. Theorem 5.3 requires at most μ|H_P| vertices of degree below (1−√γ)(p^2μ/10)|H_P|, but the paper only proves degree concentration (P3) on the 'good' intervals [2s,n/2−s], [n/2+2s,n−s], and [2s,n−2s]. The boundary intervals [1,2s−1], [n/2−s+1,n/2], [n/2+1,n/2+2s−1], and the corresponding colour intervals contain Θ(s)=Θ(μ|H_P|) vertices whose typical degree can be much smaller than the threshold; no bound on the number of such low-degree vertices is given. This is not a cosmetic issue: if all boundary vertices are below threshold, their number can exceed μ|H_P|. The lemma needs a separate estimate for these vertices, or an absorption argument that weakens the hypothesis.
[§5.1, McDiarmid step (5.3)] The claimed 2-Lipschitz property for d_{H_P}(b) is not justified as written. The product space over which McDiarmid is applied includes the coordinate corresponding to b itself; if that coordinate is switched from 'b∈S2' to 'b∉S2', then d_{H_P}(b) changes from its full value to 0, which can be as large as O(p^2s), not 2. If the intention is to condition on b being in S2 and apply McDiarmid over the remaining random vertices, this should be stated explicitly and the Lipschitz constant should be derived for all varying coordinates. The current text makes the concentration argument formally invalid.
[§5.1, Theorem 5.3] The proof of Theorem 5.3 contains an impossible inequality. The chain derives that e(H)/χ'(H) is at least (1−μ)(n/r) times (1−γ)/(1+γ+o(1)) and then claims this is at least (1−μ)·2n/r. Since (1−γ)/(1+γ)<1, this cannot hold. The intended bound is that, with γ≪μ, the factor (1−μ)(1−γ)/(1+γ) is at least (1−2μ), giving the desired (1−2μ)n/r. The factor '2' should be replaced by '1−2μ' (or similar), and the corresponding size condition on n adjusted. This is a serious error in a quoted theorem, although the theorem itself is standard and the proof is repairable.

minor comments (5)

[§5.1, last paragraph of Lemma 5.4] The per-class coverage bound follows from the total bound, but the text skips the arithmetic. Since a matching covers equally many vertices in each of the three classes, the number uncovered per class is at most (1/3)·2μ(|S1|+2|S2|) ≤ 2μ max{|S1|,|S2|}. The paper should spell this out; as it stands the inference is terse but valid.
[§5.2, end of Lemma 5.6] The final containment is written as K[˜n]∪{0}⊆K[(1+ε/2)n]∪{0}, but the lemma statement and the preceding bound give K[˜n]∪{0}⊆K[(1+ε)n]∪{0}. The ε/2 appears to be a typographical remnant and should be corrected.
[§6, last line] The final sentence says 'all but at most εn edges have distinct colours', which yields at least n−1−εn distinct colours, just short of (1−ε)n. The argument can be patched by applying the previous steps with a slightly smaller ε (e.g. ε/2) or by tracking the number of repeated colours more carefully. Please adjust the constants.
[§2.2, Notation] The hierarchy notation 0<a≪b≤1 is introduced without stating explicitly that all constants are positive and can be chosen from right to left. This is standard but should be stated in one sentence, as the paper relies heavily on it.
[§5.3, line after (5.10)] In the embedding of root vertices, the sentence 'This is possible because d'≤d=|I'_j|' assumes d' is an integer and the interval I'_j has size d, which is correct, but it may help the reader to recall that I'_j was defined with exactly d elements after removing the last 3|S| labels. No change needed beyond clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is a genuine derivation from external probabilistic and structural tools.

full rationale

The paper's derivation chain is self-contained in the relevant sense: Theorem 1.3 is reduced to Lemma 1.4 by an explicit leaf-removal argument, and Lemma 1.4 is reformulated as Lemma 1.7 via the difference-coloured complete graph. This reformulation is a change of language, not a circular input: an injective labelling into [n] with distinct edge-differences is exactly a rainbow embedding in K_[n], so using the two interchangeably is definitional rather than question-begging. The main work is Lemma 5.9, which embeds the forest obtained from the tree-splitting Lemma 4.1 into K_{[(1+ε)n]}, using Lemma 5.6, Proposition 5.8, and Lemma 5.4. Lemma 5.4 is proved from Theorem 5.3 (Pippenger/Molloy–Reed), which is an external standard hypergraph matching theorem; the proof then applies Chernoff and McDiarmid bounds and does not assume the conclusion of Theorem 1.3. Lemma 4.1 is proved from elementary tree facts, Fact 4.4, and Cayley's formula, again independently. No parameter is fitted to a target quantity and then called a prediction; no input is defined in terms of the output; no uniqueness or ansatz is imported from the authors' prior work. The only citation involving a co-author of the present paper is [15], the Ringel conjecture theorem, and it is used only as background context, not as a load-bearing premise. The reader's and skeptic's concerns are about correctness of probabilistic details in Lemma 5.4, not about circularity: even if the McDiarmid Lipschitz step or low-degree bound needed repair, that would not make the theorem's derivation equivalent to its own inputs. Thus no circularity step can be exhibited under the required standard.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No empirical free parameters. The hierarchy constants ε,δ,ζ,λ,γ,µ,d,Δ_i are chosen to satisfy explicit inequalities and vanish in the limit; none is fitted to observed data or to a target value of gs(T). No new physical or mathematical entities are postulated; the difference-coloured complete graph K_X is a definition/reformulation, not an entity with independent evidence requirements.

assumptions (6)

standard math Chernoff bound for binomial tails
Used throughout Section 5 (Theorem 2.1).
standard math McDiarmid's bounded-differences inequality
Used in Lemma 5.4, Claim 5.5 (Theorem 2.2).
standard math Pippenger's almost-perfect matching theorem for linear uniform hypergraphs
Theorem 5.3, stated as a variant of an unpublished result; used to find large rainbow matchings.
standard math Molloy–Reed near-optimal chromatic index bound for hypergraphs
Used in the proof of Theorem 5.3 to bound the number of colours in a proper edge-colouring.
standard math Cayley's formula and rooted-tree counting
Used in Lemma 4.7 and Lemma 5.6 to bound the number of rooted tree types by m^m.
ad hoc to paper The integer intervals A,B,C in H[n][A,B,C] may be treated as three disjoint vertex classes even when they overlap as subsets of [n]
Observation 5.1 defines a 3-partite hypergraph with vertex classes A,B,C; but in Lemma 5.2/5.4, A⊂C and B⊂C. The proof requires a cloned-vertex interpretation; without it, edges with c=a collapse to 2-sets. This is an unstated modeling assumption.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the gracesize of trees." pith.science (2026). https://pith.science/paper/UCZNU2TY

@misc{pith2026251111331,
  author       = {Pith},
  title        = {Pith review of: On the gracesize of trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UCZNU2TY}},
  note         = {Machine review of arXiv:2511.11331}
}

abstract

An $n$-vertex tree $T$ is said to be $\textit{graceful}$ if there exists a bijective labelling $\phi:V(T)\to \{1,\ldots,n\}$ such that the edge-differences $\{|\phi(x)-\phi(y)| : xy\in E(T)\}$ are pairwise distinct. The longstanding graceful tree conjecture, posed by R\'{o}sa in the 1960s, asserts that every tree is graceful. The $\textit{graceful}$ of an $n$-vertex tree $T$, denoted $\operatorname{gs}(T)$, is the maximum possible number of distinct edge-differences over all bijective labellings $\phi:V(T)\to \{1,\ldots,n\}$. The graceful tree conjecture is therefore equivalent to the statement that $\operatorname{gs}(T)=n-1$ for all $n$-vertex trees. We prove an asymptotic version of this conjecture by showing that for every $\varepsilon>0$, there exists $n_0$ such that every tree on $n>n_0$ vertices satisfies $\operatorname{gs}(T)\geqslant (1-\varepsilon)n$. In other words, every sufficiently large tree admits an almost graceful labelling.

Figures

Figures reproduced from arXiv: 2511.11331 by the authors.

**Figure 3.** Rainbow matching between intervals I0 and I2 for ℓ = 7, with colour set {11, 12, . . . , 17}. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗

**Figure 4.** Intervals I0, . . . , I3 depicted around the semi-circle, with subintervals I ′ 0 , I ′ 2 and I ′ 3 highlighted in orange. Vertices in S are embedded into I ′ 0 . In this example, v is adjacent to the vertices labelled by 2 and by 3 in Taux, and we embed the root vertices corresponding to these vertex sets into I ′ 2 and I ′ 3 respectively. Blue edges have a colour in C02, and lighter blue edges have larger colours … view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

A proof of Andersen's rainbow path conjecture for large $n$
math.CO 2026-08 conditional novelty 8.0 of 10

For all sufficiently large n, every properly edge-coloured n-vertex complete graph has a rainbow path on n-1 vertices, resolving Andersen's conjecture and its Latin-square analogue for large n.

Reference graph

Works this paper leans on

18 extracted references · cited by 1 Pith paper

[1]

Adamaszek, P

A. Adamaszek, P. Allen, C. Grosu, and J. Hladk` y. Almost all trees are almost graceful.Random Structures & Algorithms, 56(4):948–987, 2020. 2

2020
[2]

Alon and R

N. Alon and R. Yuster. On a hypergraph matching problem.Graphs and Combinatroics, 21(4):377–384, 2005. 10

2005
[3]

Van Bussel

F. Van Bussel. Relaxed graceful labellings of trees.Electronic Journal of Combinatorics, 9(1):12, 2002. 2

2002
[4]

G. Dirac. Some theorems on abstract graphs.Proceedings of the London Mathematical Society, 3(1):69–81,
[5]

Erd˝ os, P

P. Erd˝ os, P. Hell, and P. Winkler. Bandwidth versus bandsize.Annals of Discrete Mathematics, 41:117–129,
[6]

Erd˝ os, M

P. Erd˝ os, M. Simonovits, and V.T. S´ os. Anti-Ramsey theorems.Infinite and finite sets, 2:633–643, 1975. 1

1975
[7]

J. Gallian. A dynamic survey of graph labeling.Electronic Journal of Combinatorics, 25:9–46, 2022. 2

2022
[8]

S. Golomb. How to number a graph. InGraph Theory and Computing, pages 23–37. Academic Press, 1972. 1

1972

Show all 18 references

[9]

Graham and N

R. Graham and N. Sloane. On additive bases and harmonious graphs.Siam Journal on Algebraic and Discrete Methods, 1, 12 1980. 1

1980
[10]

Janson, T

S. Janson, T. Luczak, and A. Rucinski.Random Graphs. Wiley New York, 2000. 5

2000
[11]

Keevash and K

P. Keevash and K. Staden. Ringel’s tree packing conjecture in quasirandom graphs.Journal of the European Mathematical Society (EMS Publishing), 27(5), 2025. 2

2025
[12]

W. Mantel. Problem 28.Wiskundige Opgaven, 10:60–61, 1907. 1

1907
[13]

McDiarmid

C. McDiarmid. On the method of bounded differences.Surveys in combinatorics, 141:148–188, 1989. 5

1989
[14]

Molloy and B

M. Molloy and B. Reed. Near-optimal list colorings.Random Structures & Algorithms, 17(3-4):376–402, 2000. 11

2000
[15]

Montgomery, A

R. Montgomery, A. Pokrovskiy, and B. Sudakov. A proof of Ringel’s conjecture.Geometric and Functional Analysis, 31:1–58, 06 2021. 2

2021
[16]

G. Ringel. Theory of graphs and its applications. InProceedings of the Symposium Smolenice, 1963. 2

1963
[17]

A. Rosa. On certain valuations of the vertices of a graph.Theory of Graphs (Internat. Symposium, Rome), page 349–355, 1966. 1

1966
[18]

Rosa and J

A. Rosa and J. ˇSir´ aˇ n. Bipartite labelings of trees and the gracesize.Journal of Graph Theory, 19(2):201–215,

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [1]

Adamaszek, P

A. Adamaszek, P. Allen, C. Grosu, and J. Hladk` y. Almost all trees are almost graceful.Random Structures & Algorithms, 56(4):948–987, 2020. 2

2020

[2] [2]

Alon and R

N. Alon and R. Yuster. On a hypergraph matching problem.Graphs and Combinatroics, 21(4):377–384, 2005. 10

2005

[3] [3]

Van Bussel

F. Van Bussel. Relaxed graceful labellings of trees.Electronic Journal of Combinatorics, 9(1):12, 2002. 2

2002

[4] [4]

G. Dirac. Some theorems on abstract graphs.Proceedings of the London Mathematical Society, 3(1):69–81,

[5] [5]

Erd˝ os, P

P. Erd˝ os, P. Hell, and P. Winkler. Bandwidth versus bandsize.Annals of Discrete Mathematics, 41:117–129,

[6] [6]

Erd˝ os, M

P. Erd˝ os, M. Simonovits, and V.T. S´ os. Anti-Ramsey theorems.Infinite and finite sets, 2:633–643, 1975. 1

1975

[7] [7]

J. Gallian. A dynamic survey of graph labeling.Electronic Journal of Combinatorics, 25:9–46, 2022. 2

2022

[8] [8]

S. Golomb. How to number a graph. InGraph Theory and Computing, pages 23–37. Academic Press, 1972. 1

1972