Trees of odd order with at most two vertices of degree two are edge-graceful

Lingsen Meng

REVIEW 1 major objections 5 minor 14 references

Trees of odd order with at most two vertices of degree two are edge-graceful

T0 review · 1 major / 5 minor · reviewed 2026-08-28 · deepseek-v4-flash

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

Pith's one-line read The paper proves that every tree of odd order with at most two degree-two vertices is edge-graceful.

desk verdict New extension of Lee's conjecture from one to two degree-two vertices, with a clean explicit construction; the only real risk is the uniformity claim in the large-n packing lemma. read the letter →

arxiv 2608.23881 v1 pith:W4E2NEXP submitted 2026-08-24 math.CO

Lingsen Meng This is my paper · ORCID

classification math.CO MSC 05C7805C05

keywords edge-gracefullabelingantimagictreeconjecturezero-sumblockpartitionLangfordsequencestwintriplesdegree-twoverticesgraph

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

This paper proves that every tree with an odd number of vertices and at most two vertices of degree two admits an edge-graceful labeling: the edges can be numbered from 1 to n-1 so that, for each vertex, the sum of the numbers on its incident edges is distinct modulo n. This settles the next open case of a 1989 conjecture, which had previously been known only for trees with at most one degree-two vertex. The proof is constructive and modular, and because an edge-graceful labeling makes vertex sums distinct as integers as well, the result also adds these trees to the known family of antimagic trees.

What carries the argument

The load-bearing objects are the rooted reformulation, the zero-sum block decomposition, and the packing lemma. Rooting the tree at a suitable vertex turns any edge bijection into a bijection g: V -> Z_n with g(root)=0; the edge-graceful condition becomes the requirement that the induced sums h(v)=g(v)+sum of children's g-values form a permutation of Z_n. The proof forces this by giving every internal vertex a block of labels with total 0 modulo n, except for a small catalog of gadget blocks around the two degree-two vertices. The remaining label set is a disjoint union of symmetric pairs {i,n-i}, and Lemma 5 (packing) decomposes almost all of it into zero-sum triples via perfect and hooked Langford sequences and the twin-triple observation that {i,j,k} with i+j+k=n or i+j=k yields two disjoint zero-sum triples in Z_n\{0}.

What would settle it

Check Lemma 5 at a specific odd n above 301 whose residue class uses an alternate parameter, say n=5003, by exhaustively searching for the m disjoint admissible triples in the residual index set after the gadget; a single failure, or an invalid stored packing witness for any odd n between 21 and 301, would break the proof. Conversely, reproducing the branch-scan checker from the paper's plain-language description and finding no failures for all odd n up to 5001 would confirm the uniformity claim.

Watch

Extended reading notes

Core claim

The central claim, Theorem 2, is that every tree of odd order with at most two vertices of degree two is edge-graceful, hence antimagic. The argument rests on a rooted reformulation in which an edge labeling is replaced by a bijection g from the vertices to Z_n, and the desired vertex sums are forced to be a permutation of Z_n by assigning each internal vertex a block of labels whose sum is zero modulo n. The two degree-two vertices are handled by a small catalog of prescribed block patterns that leave the remaining nonzero labels as a union of symmetric pairs {i,n-i}; a packing lemma, built from perfect and hooked Langford sequences and a twin-triple identity, decomposes those pairs into zero-sum triples, and the assembly is verified constructively. The proof also includes a complete computational check on all 2,245,070 trees of odd order at most 25 with exactly two degree-two vertices and a symbolic verification of the packing branches for all odd n up to 5001, with the pattern asserted to hold uniformly beyond.

Load-bearing premise

The load-bearing premise is that Lemma 5's packing of the residual index set really works uniformly for all odd n>301; the paper supports this with a symbolic branch scan for n up to 5001 and a uniformity argument, but the residue-by-residue verification is not written out in human-readable form, so the whole theorem rests on that computer-checked case analysis being complete.

Editorial extensions

If this is right

The 1989 conjecture is now known for every tree whose number of degree-two vertices is 0, 1, or 2; the first unresolved case is three such vertices.
Every tree in this class is antimagic, since an edge-graceful labeling gives distinct vertex sums modulo n and therefore distinct integer sums; this enlarges the known antimagic-tree family.
For each such tree the proof gives an explicit algorithm: choose a catalog row, pack the residual index set, and assign blocks, so edge-graceful labelings are produced constructively.
The computational portion certifies the construction on all 2,245,070 odd-order trees of order at most 25 with exactly two degree-two vertices and provides packing witnesses for all odd orders from 21 through 301.
The method itself is not limited to two degree-two vertices: each additional one contributes a singleton block, and the paper notes the gadget would grow with the number of chains, though the bookkeeping becomes unwieldy.

Reading between the lines

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

A fresh implementation of Lemma 5 for a few odd n above 5001 would be a natural independent check; because the paper's symbolic scan stops at 5001, a new implementation would either confirm the uniformity assertion or expose a residue-class gap.
The twin-triple packing of Z_n\{0\} by zero-sum triples is a self-contained combinatorial statement that could be useful beyond tree labeling, for example in constructing difference families or sequenceable groups for cyclic groups.
The reported even-order computation, which finds only stars and one sporadic double star as exceptions to distinctness modulo n+1, suggests a possible classification result for even-order trees, though the paper makes no such claim.
For three or more degree-two vertices, the hand-written gadget catalog would probably need to be generated by search; the overall block-assembly strategy might still hold if a general chain-handling gadget exists.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

Claim #1: The central claim, Theorem 2, is that every tree of odd order with at most two vertices of degree two is edge-graceful, hence antimagic. The argument rests on a rooted reformulation in which an edge labeling is replaced by a bijection g from the vertices to Z_n, and the desired vertex sums are forced to be a permutation of Z_n by assigning each internal vertex a block of labels whose sum is zero m

/-- @claim 1 The central claim, Theorem 2, is that every tree of odd order with at most two vertices of degree two is edge-graceful, hence antimagic. The argument rests on a rooted reformulation in which an edge labeling is replaced by a bijection g from the vertices to Z_n, and the desired vertex sums are forced to be a permutation of Z_n by assigning each internal vertex a block of labels whose sum is zero m -/
def central_claim : Prop :=

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

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

Colleague — this paper is worth a look. The result is new: it pushes the known case of Lee's conjecture from at most one degree-two vertex to at most two, and it does so with a genuinely explicit construction rather than a nonconstructive existence argument. The twin-triple observation (Lemma 3) is neat, and the assembly argument (Proposition 7) is clean. The computational part is unusually thorough: every tree of odd order up to 25 with exactly two degree-two vertices is labeled and checked, with certificates and an independent checker. That is real evidence.

The soft spot is exactly what you flagged: Lemma 5(ii) carries all weight for n>301, and the uniformity claim rests on a symbolic branch scan rather than a fully expanded human proof. I read the branch plans and found no arithmetic error; the residue-class conditions align with Simpson's theorem. But a single off-by-one in a window, or a missed residue class, would break infinitely many n. The paper's own finite checks (to 5001) do not prove uniformity; they only make it highly plausible. This is a legitimate referee-level concern, not a manufactured one. It is also structurally isolated: the rest of the construction does not depend on the large-n case analysis.

I would send this to a serious referee. The result deserves to be in the literature if the uniformity claim is right, and the author has supplied enough material for a referee to verify it. My own recommendation would be acceptance after the branch-scan logic is made more directly inspectable — ideally a human-readable table of the windows and holes, or a formalized version of the residue-class argument. The paper is honest about its limitations and about the computational nature of that step.

For the reading group: maybe. It is a good example of a modern constructive labeling proof with heavy computational assistance, and a useful case study in where symbolic checking can and cannot replace a written proof. I would cite it if I worked on edge-graceful or antimagic trees.

Referee Report

1 major / 5 minor

Summary. The paper proves that every tree of odd order with at most two vertices of degree two admits an edge-graceful labeling, and hence is antimagic. The proof proceeds through a rooted reformulation in which an edge labeling is encoded by a bijection g:V→Z_n and vertex sums are analyzed blockwise. A small gadget catalog absorbs the two degree-two vertices, and a packing lemma (Lemma 5) decomposes residual index sets into zero-sum pairs and triples using perfect and hooked Langford sequences. The paper also reports a complete computer verification for all 2,245,070 trees of odd order at most 25 with exactly two degree-two vertices, packing witnesses for 27≤n≤301, and a symbolic branch check for odd n≤5001 that is asserted to hold uniformly beyond.

Significance. If the proof is correct, this is a substantial advance on Lee's 1989 conjecture: Theorem 1 of Kaplan–Lev–Roditty covered trees with at most one vertex of degree two, and the present paper settles the next natural case for all trees of odd order with exactly two degree-two vertices. The construction is explicit and parameter-free, and the twin-triple observation in Lemma 3 is an elegant and reusable tool for converting Langford-type decompositions into zero-sum subsets of Z_n. The computational verification is unusually thorough: per-tree certificates with SHA-256 manifests, an independent checker, packing witnesses, and a branch-scan checker are provided. There is no circularity: the proof relies on external theorems (Simpson's Langford existence theorem, the Kaplan–Lev–Roditty result) whose statements are independent of the new theorem. If the uniformity claim in Lemma 5 is made fully explicit, the paper would be a clear accept.

major comments (1)

[Lemma 5(ii), proof, 'Regimen n>301'] The uniform-in-n part of the packing lemma is load-bearing for every n>301, but the text states that the window arithmetic of every branch 'was checked symbolically for all odd n≤5001 and is uniform in n beyond' without writing out the inequalities or the complete residue-class verification. I checked the listed branch plans arithmetically and found them consistent, but the manuscript does not provide a human-readable derivation of the uniformity: for each of the four shapes and each residue class of (m mod 4, e), the reader would need to see the exact intervals, the Langford or hooked Langford parameters, and the verification that Simpson's conditions hold for all n>301. As written, the uniformity claim is an assertion based on a symbolic scan rather than a fully expanded proof. Please either include this derivation in an appendix or supply a formally verified certificate for the branch-scan checker, so that the infinite uniformity statement is independently checkable without rerunning unpublished code.

minor comments (5)

[Table 1] The abbreviations NA and ADJ are used in the table but never defined in the caption; please define them as 'non-adjacent' and 'adjacent' for the two degree-two vertices.
[Lemma 5, proof, 'Regime 27≤n≤301'] The sentence 'Over 21≤n≤301' appears immediately after the lemma states n≥27 and may confuse the reader; clarify that this sentence concerns the packing computations for the small cases handled by Theorem 2, not the regime of Lemma 5 itself.
[Section 4, paragraph 'It remains to build g'] The assertion that the gadget parameters 'must keep all listed elements distinct and nonzero, which for the displayed primary and alternate choices is a finite check' would be easier to verify if the finite inequalities (for example, α, β, w staying below K and avoiding prescribed collisions) were listed explicitly.
[Section 5] The sentence describing the four exceptional instances would be clearer if the exceptions were displayed with their ground sets in a small table or list, since they are referenced in multiple places (Lemma 5 proof and Section 5).
[Section 6, Remark (2)] The claim that an edge-graceful labeling is antimagic is stated in the introduction and used in Theorem 2, but no original citation is given; adding a reference to the antimagic-tree literature (or to Gallian's survey) would be helpful.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained and rests on independent external theorems.

full rationale

I walked the derivation chain of Theorem 2. The proof combines (a) a rooted reformulation that is a direct bijective translation of edge-graceful labelings, (b) Lemma 3 (twin triples), which is proved explicitly by a computation and a converse argument, (c) Lemma 5 (packing), which is established by explicit Langford/hooked-Langford window constructions using Simpson's external theorem for n>301 and by re-verifiable computer witnesses for n<=301, and (d) Proposition 7 and the gadget catalog, whose prescribed block sums are checked by direct arithmetic. None of these steps assumes the statement of Theorem 2, and no parameter is fitted to the data being predicted. The external theorems cited (Simpson's Langford existence theorem; Kaplan-Lev-Roditty's Z_n-antimagic tree theorem) are independent mathematical results with published proofs, not self-citations, and the only self-citation is the Zenodo archive of supplementary certificates, which is not load-bearing for the proof. The residual large-n uniformity in Lemma 5 is verified by a symbolic branch scan for all odd n<=5001 and asserted to be uniform beyond; this is a verification/completeness risk, not a circularity, because it does not reduce the theorem to its own assumption. The finite computations over all 2,245,070 trees of odd order at most 25 are corroborating evidence, not inputs to the general proof. There is therefore no step in which a prediction or derived result is equivalent by construction to the paper's inputs, no fitted parameter renamed as a prediction, and no load-bearing self-citation chain. Score 0.

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

The construction relies on two cited results (Simpson, Kaplan-Lev-Roditty) and on standard parity facts about trees. No new entities are introduced. The gadget constants (alpha=1 or 2, beta=3 or -1, w=3 or 5, u=1 or 5) are fixed explicit choices that satisfy the required sums for all odd n>=21; they are not fitted to data.

assumptions (3)

standard math Theorem 4 (Simpson 1983): existence of perfect and hooked Langford sequences is completely characterized.
Used in Lemma 5 to construct packings of residual intervals [5,K], [4,K], [3,K], and {2} union [7,K].
standard math Theorem 1 (Kaplan-Lev-Roditty 2009): every tree of odd order with at most one vertex of degree two is edge-graceful.
Covers the 0 or 1 degree-two cases in Theorem 2; the paper proves the new exactly-two case.
standard math Lo's necessary condition for edge-graceful labelings: q(q+1) is congruent to p(p-1)/2 modulo p.
Background for why only odd-order trees can be edge-graceful; not used in the construction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Trees of odd order with at most two vertices of degree two are edge-graceful." pith.science (2026). https://pith.science/paper/W4E2NEXP

@misc{pith2026260823881,
  author       = {Pith},
  title        = {Pith review of: Trees of odd order with at most two vertices of degree two are edge-graceful},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W4E2NEXP}},
  note         = {Machine review of arXiv:2608.23881}
}

read the original abstract

A graph G with q edges and p vertices is edge-graceful if some bijection f from E(G) onto {1,...,q} makes the induced vertex sums f^+(v), the sum of f(e) over the edges e incident to v, distinct modulo p. Lee conjectured in 1989 that every tree of odd order is edge-graceful; the broadest general result we have located, due in equivalent form to Kaplan, Lev and Roditty, covers trees of odd order with at most one vertex of degree two. We prove that every tree of odd order with at most two vertices of degree two is edge-graceful. The proof combines zero-sum block partitions of Z_n with perfect and hooked Langford sequences; the residual case analysis is verified symbolically for all odd n <= 5001 and holds uniformly beyond, and the construction was executed and independently re-checked on all 2,245,070 trees of odd order at most 25 with exactly two vertices of degree two. Since an edge-graceful graph is antimagic, the theorem also enlarges the family of trees known to be antimagic.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

Cabaniss, R

S. Cabaniss, R. Low, J. Mitchem, On edge-graceful regular graphs and trees,Ars Combin. 34(1992) 129–142

work page 1992
[2]

J. A. Gallian, A dynamic survey of graph labeling,Electron. J. Combin.(2025), #DS6, 28th ed

work page 2025
[3]

Helms, H

T. Helms, H. Jordon, M. Murray, S. Zeppetello, Extended Skolem-type difference sets, Australas. J. Combin.53(2012) 221–235

work page 2012
[4]

Kaplan, A

G. Kaplan, A. Lev, Y. Roditty, On zero-sum partitions and anti-magic trees,Discrete Math. 309(2009) 2010–2014

work page 2009
[5]

Keene, A

J. Keene, A. Simoson, Balanced strands for asymmetric, edge-graceful spiders,Ars Combin. 42(1996) 49–64

work page 1996
[6]

S. M. Lee, A conjecture on edge-graceful trees,Scientia3(1989) 45–47

work page 1989
[7]

Liang, T.-L

Y.-C. Liang, T.-L. Wong, X. Zhu, Anti-magic labeling of trees,Discrete Math.331(2014) 9–14

work page 2014
[8]

Lo, On edge-graceful labelings of graphs,Congr

S. Lo, On edge-graceful labelings of graphs,Congr. Numer.50(1985) 231–241

work page 1985

Show all 14 references

[9]

Meng, Supplementary material for: Trees of odd order with at most two vertices of degree two are edge-graceful, Zenodo, v1.0.0, 2026,doi:10.5281/zenodo.22085671

[dataset] L. Meng, Supplementary material for: Trees of odd order with at most two vertices of degree two are edge-graceful, Zenodo, v1.0.0, 2026,doi:10.5281/zenodo.22085671

2026 doi
[10]

Morgan, Gracefully labeled trees from Skolem sequences,Congr

D. Morgan, Gracefully labeled trees from Skolem sequences,Congr. Numer.142(2000) 41–48

2000
[11]

Morgan, R

D. Morgan, R. Rees, Using Skolem and Hooked-Skolem sequences to generate graceful trees, J. Combin. Math. Combin. Comput.44(2003) 47–63

2003
[12]

Peltesohn, Eine L¨ osung der beiden Heffterschen Differenzenprobleme,Compos

R. Peltesohn, Eine L¨ osung der beiden Heffterschen Differenzenprobleme,Compos. Math.6 (1939) 251–257

1939
[13]

J. E. Simpson, Langford sequences: perfect and hooked,Discrete Math.44(1983) 97–104

1983
[14]

Small, Regular (even) spider graphs are edge-graceful,Congr

D. Small, Regular (even) spider graphs are edge-graceful,Congr. Numer.74(1990) 247– 254. 7

1990

Pith tools

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

[1] [1]

Cabaniss, R

S. Cabaniss, R. Low, J. Mitchem, On edge-graceful regular graphs and trees,Ars Combin. 34(1992) 129–142

work page 1992

[2] [2]

J. A. Gallian, A dynamic survey of graph labeling,Electron. J. Combin.(2025), #DS6, 28th ed

work page 2025

[3] [3]

Helms, H

T. Helms, H. Jordon, M. Murray, S. Zeppetello, Extended Skolem-type difference sets, Australas. J. Combin.53(2012) 221–235

work page 2012

[4] [4]

Kaplan, A

G. Kaplan, A. Lev, Y. Roditty, On zero-sum partitions and anti-magic trees,Discrete Math. 309(2009) 2010–2014

work page 2009

[5] [5]

Keene, A

J. Keene, A. Simoson, Balanced strands for asymmetric, edge-graceful spiders,Ars Combin. 42(1996) 49–64

work page 1996

[6] [6]

S. M. Lee, A conjecture on edge-graceful trees,Scientia3(1989) 45–47

work page 1989

[7] [7]

Liang, T.-L

Y.-C. Liang, T.-L. Wong, X. Zhu, Anti-magic labeling of trees,Discrete Math.331(2014) 9–14

work page 2014

[8] [8]

Lo, On edge-graceful labelings of graphs,Congr

S. Lo, On edge-graceful labelings of graphs,Congr. Numer.50(1985) 231–241

work page 1985