arxiv: 2605.14295 · v1 · submitted 2026-05-14 · 🧮 math.CO

Recognition: 1 theorem link

· Lean Theorem

Graceful Labeling of Two Families of Spiders

Singling Shan , Yucheng Zhong

Authors on Pith no claims yet

Pith reviewed 2026-05-15 02:45 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C78

keywords graceful labelingspider graphsgraceful tree conjecturepath attachmentalpha-labelingstrees

0 comments

The pith

Spiders with sufficiently rapidly increasing leg lengths are graceful.

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

The paper establishes that two families of spider graphs admit graceful labelings. Spiders are trees with a single central vertex and several path legs of varying lengths attached to it. The authors first prove a relaxed attachment result: under a mild bound on a vertex label in a graceful graph G and when the path length n is not congruent to 1 modulo 4, attaching a path to that vertex yields another graceful graph. They then apply this construction to show that spiders whose successive legs satisfy the given doubling-plus-constant edge-count inequalities are graceful. This adds concrete new cases to the graceful tree conjecture, which asserts that every tree has a graceful labeling.

Core claim

Any spider with legs L1,...,Ls (s >= 1) satisfying |E(L2)| >= 2|E(L1)| + 4 and |E(Li+1)| >= 2|E(Li)| + 2 for i in {2,...,s-1} is graceful. The paper also supplies an explicit graceful labeling for the family of spiders that have one leg of arbitrary length and all remaining legs of length at most two, with the center vertex labeled 0; this labeling permits further attachments of paths at the center while preserving gracefulness.

What carries the argument

The relaxed path-attachment theorem: if G is graceful under labeling f and f(u) + floor(n/2) + 1 <= n with n not congruent to 1 modulo 4, then joining u to an endpoint of a disjoint n-vertex path produces a graceful graph.

Load-bearing premise

The attachment construction requires that the path length n is not congruent to 1 modulo 4, and the spiders must satisfy the stated leg-length growth inequalities.

What would settle it

A concrete spider satisfying the leg inequalities for which no graceful labeling exists, or a computation showing the attachment fails for some allowed n and some graceful G.

Figures

Figures reproduced from arXiv: 2605.14295 by Singling Shan, Yucheng Zhong.

**Figure 1.** Figure 1: An illustration of the labeling h. Next we verify that h(E(G′ )) = [1, m + n]. As h(x) = f(x) + ⌊ n 2 ⌋ for all x ∈ V (G) and f(E(G)) = [1, m], we have h(E(G)) = [1, m]. As g is an α-labeling of Pn, by the definition of h, we have h(E(Pn)) = m + 1 + [1, n − 1] = [m + 2, m + n]. Furthermore, we have h(u) = f(u) + ⌊ n 2 ⌋ and h(v) = g(v) + m + 1 = f(u) + ⌊ n 2 ⌋ + m + 1 since g(v) ≥ ⌊ n 2 ⌋, and so h(uv) = m… view at source ↗

**Figure 2.** Figure 2: An illustration of naming the vertices of [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: A graceful labeling of S when s = 2 and ℓ = 11. For any i ∈ [1, s], let f(ui) = m − 2(i − 1), f(vi) = 2i − 1; and for any i ∈ [0, ℓ], let f(xi) =    2 × i 4 = i 2 if i ≡ 0 (mod 4), m − 2s − 2 × i−1 4 = m − 2s − i−1 2 if i ≡ 1 (mod 4), 2s − 1 + 2 × i+2 4 = 2s − 1 + i+2 2 if i ≡ 2 (mod 4), m − 1 − 2 × i−3 4 = m − 1 − i−3 2 if i ≡ 3 (mod 4). See [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

**Figure 4.** Figure 4: A graceful labeling of S when s = 2 and ℓ = 10. In the remainder of the proof, we verify that f is a graceful labeling of S. Before proceed to the proof, we define a partition of V (S) and E(S) as follows. Let U = {ui : i ∈ [1, s]}, V = {vi : i ∈ [1, s]}, and Wj = {xi : i ∈ [1, ℓ], i ≡ j (mod 4)}, j ∈ [0, 3]; and E1 = {x0ui : i ∈ [1, s]}, E2 = {uivi : i ∈ [1, s]}, Fj = {xixi+1 : i ≡ j (mod 4)}, j ∈ [0, 3].… view at source ↗

read the original abstract

A \emph{graceful labeling} of a graph $G$ is an injective function $f : V(G) \to \{0, \ldots, |E(G)|\}$ such that $\{\,|f(u)-f(v)| : uv \in E(G)\,\} = \{1, \ldots, |E(G)|\}$. If such a labeling exists, then we call $G$ \emph{graceful}. Introduced by Rosa in 1967, graceful labeling has been widely studied, and the Graceful Tree Conjecture asserts that every tree is graceful. The conjecture is known to hold for several classes of trees, including caterpillars, trees with at most four leaves, trees of diameter at most five, and certain spiders. An important subclass is that of \emph{$\alpha$-labelings}, where a graceful labeling $f$ admits an integer $\alpha$ such that each edge joins a vertex with label at most $\alpha$ to one with label greater than $\alpha$. A result from 1982 by Huang, Kotzig, and Rosa shows that if $H$ has an $\alpha$-labeling with a vertex $u$ labeled $0$ or $\alpha$, and $G$ has a graceful labeling with a vertex $v$ labeled $0$, then identifying $u$ and $v$ yields a graceful graph, though this requires a $0$-labeled vertex in $G$. We prove a related result that relaxes this condition: if $G$ has a graceful labeling $f$ such that $f(u)+\lfloor n/2 \rfloor + 1 \le n$ and $n \not\equiv 1 \pmod{4}$, where $u\in V(G)$ and $n\ge 2$ is an integer, then joining $u$ to an end vertex of the vertex-disjoint $n$-vertex path $P_n$ yields a graceful graph. As an application, we show that any spider with legs $L_1,\ldots,L_s$ ($s \ge 1$) satisfying $|E(L_{2})| \ge 2|E(L_1)|+ 4$ and $|E(L_{i+1})| \ge 2|E(L_i)|+ 2$ for $i \in \{2,\ldots, s-1\}$ is graceful. Furthermore, we give an explicit graceful labeling for spiders with one leg of arbitrary length and all others of length at most two such that the center is labeled by $0$. This labeling enables the construction of larger graceful spiders by attaching paths at the center.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Shan and Zhong relax the 1982 attachment condition and prove gracefulness for two narrow families of spiders.

read the letter

The main takeaway is that this paper relaxes the Huang-Kotzig-Rosa attachment rule from 1982 and applies the new version to two specific families of spiders. Instead of requiring a 0-labeled vertex in the base graph, they allow attaching an n-path to a vertex u when f(u) is small enough relative to n and n is not congruent to 1 mod 4. They then use this to show that spiders whose leg lengths grow rapidly enough are graceful, and they give an explicit 0-centered labeling for the case with one long leg and the rest short.

Referee Report

1 major / 3 minor

Summary. The paper proves a relaxation of the Huang-Kotzig-Rosa 1982 theorem: if a graph G admits a graceful labeling f with f(u) + floor(n/2) + 1 ≤ n and n ≢ 1 (mod 4), then the graph obtained by attaching an n-vertex path at u is graceful. It applies this result inductively to show that any spider whose legs L1,…,Ls satisfy |E(L2)| ≥ 2|E(L1)| + 4 and |E(L_{i+1})| ≥ 2|E(Li)| + 2 for i ≥ 2 is graceful. The paper also supplies an explicit 0-centered graceful labeling for the family of spiders having one leg of arbitrary length and all remaining legs of length at most 2.

Significance. If the claims hold, the work enlarges the known graceful spiders and supplies a flexible attachment lemma that may be reusable for other trees. The constructive nature of both the relaxed theorem and the explicit one-long-leg labeling constitutes a concrete advance toward the Graceful Tree Conjecture.

major comments (1)

§3, Theorem 3.1: the inductive step that selects the path length n meeting both the congruence condition and the label bound f(u) + floor(n/2) + 1 ≤ n is only sketched; an explicit formula or algorithm for choosing n from the leg-length inequalities would make the construction fully verifiable.

minor comments (3)

The definition of a spider (center vertex plus paths) is introduced only in §4; moving a brief formal definition to the introduction would improve readability.
Notation: the symbol n is used both for the path length in the relaxed theorem and for the total number of edges in some spider statements; a local redefinition or subscript would eliminate ambiguity.
The explicit labeling in §5 is given by a table of vertex labels; adding a short paragraph describing the pattern (e.g., alternating high-low assignments on the long leg) would make the construction easier to follow without the table.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We are grateful to the referee for the thorough review and the recommendation for minor revision. We address the single major comment below and will incorporate the suggested clarification in the revised version.

read point-by-point responses

Referee: §3, Theorem 3.1: the inductive step that selects the path length n meeting both the congruence condition and the label bound f(u) + floor(n/2) + 1 ≤ n is only sketched; an explicit formula or algorithm for choosing n from the leg-length inequalities would make the construction fully verifiable.

Authors: We agree that an explicit selection rule for n would enhance the clarity and verifiability of the inductive construction. In the revised manuscript, we will include an explicit algorithm: given the current labeling with f(u) = k, set m = 2k + 2. Let n be the smallest integer n ≥ m such that n ≢ 1 (mod 4). This n satisfies the bound k + floor(n/2) + 1 ≤ n because n ≥ 2k + 2 implies floor(n/2) ≤ n - k - 1. The congruence condition is satisfied by choice of n. The leg-length inequalities ensure that each inductive step has a sufficiently long leg to attach, allowing this choice of n at every stage. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation cites the external 1982 Huang-Kotzig-Rosa theorem on alpha-labelings and proves an independent relaxation requiring only n ≢ 1 mod 4 together with a bound on f(u). The spider leg-length inequalities are selected precisely to guarantee that suitable path lengths satisfying the congruence can be chosen in the constructive attachment; they are not fitted parameters or self-definitions. An explicit 0-centered labeling is supplied for the base case and used to bootstrap larger spiders. No equation reduces the claimed graceful labelings to prior inputs by construction, and the central argument remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on the standard definitions of graphs, trees, spiders, and graceful labelings together with the 1982 Huang-Kotzig-Rosa theorem; no free parameters, new entities, or ad-hoc axioms are introduced.

axioms (2)

standard math Standard definitions of graphs, trees, spiders, and graceful labelings from graph theory.
The paper operates entirely within established combinatorial definitions.
domain assumption The 1982 result of Huang, Kotzig, and Rosa on alpha-labelings and identification of graceful graphs.
The new relaxed construction is presented as a direct extension of this prior theorem.

pith-pipeline@v0.9.0 · 5790 in / 1397 out tokens · 30890 ms · 2026-05-15T02:45:35.022666+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

any spider with legs L1,...,Ls (s >= 1) satisfying |E(L2)| >= 2|E(L1)| + 4 and |E(Li+1)| >= 2|E(Li)| + 2 ... is graceful

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

Bahls, S

P. Bahls, S. Lake, and A. Wertheim. Gracefulness of families of spiders.Involve, 3(3):241–247, 2010

work page 2010
[2]

R. Cattell. Graceful labellings of paths.Discrete Math., 307(24):3161–3176, Nov. 2007

work page 2007
[3]

J. A. Gallian. A dynamic survey of graph labeling.Electronic Journal of Combinatorics, DS6, 2025. 28th edition, October 30, 2025

work page 2025
[4]

S. W. Golomb. How to number a graph.Graph theory and computing, pages 23–37, 1972

work page 1972
[5]

Hrnc´ ıar and A

P. Hrnc´ ıar and A. Haviar. All trees of diameter five are graceful.Discrete Mathematics, 233:133–150, 2001

work page 2001
[6]

Huang, A

C. Huang, A. Kotzig, and A. Rosa. Further results on tree labelings.Utilitas Mathe- matica, 21:31–48, 1982

work page 1982
[7]

Panpa, S

A. Panpa, S. Imnang, and T. Wasuanankul. Graceful labeling of spider graphs with at most five legs.Journal of Applied Mathematics, page 5, 2025. 16

work page 2025
[8]

Panpa and T

A. Panpa and T. Poomsa-ard. On graceful spider graphs with at most four legs of lengths greater than one.Journal of Applied Mathematics, 3:1–5, 2016

work page 2016
[9]

Ringel.Theory of Graphs and Its Applications

G. Ringel.Theory of Graphs and Its Applications. 1964

work page 1964
[10]

A. Rosa. On certain valuations of the vertices of a graph.Theory of Graphs (Internat. Sympos., Rome, 1966), pages 349–355, 1967

work page 1966
[11]

A. Rosa. Labeling snakes.Ars Combinatoria, 3:67–74, 1977

work page 1977
[12]

Saengsura and T

K. Saengsura and T. Poomsa-ard. Graceful labeling of some spider graphs.European Journal of Pure and Applied Mathematics, 18(2):5305, 2025. 17

work page 2025