The Graceful Tree Conjecture

Graceful Tree Conjecture

Definitions and mathematical statement

Let $T=(V,E)$ be a finite tree, meaning a nonempty simple connected graph with no cycle. Write $m=|E|$, so $|V|=m+1$. A graceful labelling is an injective function \[ f:V\longrightarrow\{0,1,\ldots,m\} \] for which the induced edge labels $|f(u)-f(v)|$, $uv\in E$, are pairwise distinct. Since there are $m$ edges and each edge difference lies in $\{1,\ldots,m\}$, this is equivalent to requiring \[ \{|f(u)-f(v)|:uv\in E\}=\{1,\ldots,m\}. \] For a tree the vertex labelling is necessarily a bijection, since domain and codomain have the same size.

The Graceful Tree Conjecture states that every finite tree admits a graceful labelling. Both the vertex labels and the absolute edge differences must satisfy the specified conditions simultaneously. Repeated vertex labels are forbidden even if the edge differences happen to be distinct.

The one-vertex tree, with $m=0$, has the label zero and no edges, so it satisfies the definition vacuously. In general, no root, orientation, or ordering of the vertices is prescribed; the labelling may be chosen freely to suit the tree. Enlarging the label interval or allowing fewer than $m$ distinct edge differences would give weaker labelling problems. The target here requires exactly the interval from zero to $m$ and every positive difference in that interval once.

Short English statement

Can every tree be numbered from zero to its number of edges so the differences across its edges are exactly all positive labels, without repetition?

Research attempt

Scope and method.

This research attempt by GPT-6 Astra Ultra is dated 1 October 2026. It preserves the catalogue statement and distinguishes elementary proofs below from cited prior work. No novelty claim or formal proof-assistant verification is made. The final paragraph states the precise remaining scope.

Literature and constructive target.

The catalogue source attributes graceful tree labelling to Kotzig, Ringel and Rosa. The primary paper [R1] studies additional restricted tree families. Here we construct explicit labellings for paths and all double-stars, prove a cyclic decomposition consequence, and test the most immediate leaf-extension strategy. The constructions are elementary known cases, not evidence that all tree shapes have been covered.

Paths and double-stars.

For a path with $m$ edges, assign labels along it as $0,m,1,m-1,2,m-2,\ldots$, stopping when all $m+1$ labels are used. Successive absolute differences are $m,m-1,\ldots,1$, so the labelling is graceful. The single vertex with $m=0$ is labelled zero.

For a double-star, let its adjacent centres $u,v$ have respectively $a,b$ additional leaf neighbours; thus $m=a+b+1$. Assign \[ f(u)=0,\qquad f(v)=b+1, \] give the $b$ leaves at $v$ labels $1,\ldots,b$, and give the $a$ leaves at $u$ labels $b+2,\ldots,m$. Every integer from zero to $m$ is used once. The differences at $v$ are $1,\ldots,b$; the centre edge has difference $b+1$; and the differences at $u$ are $b+2,\ldots,m$. These three sets partition the required edge labels. Empty leaf sets cause no problem, so stars and the one-edge tree are included. This proves all trees of diameter at most three, since deleting the central edge of such a tree leaves two stars (with a star or single vertex as the degenerate cases).

A cyclic consequence with an exact count.

Suppose a tree with $m\ge1$ edges has a graceful labelling. Regard its labels as residues modulo $N=2m+1$ and translate all labels by each $t\in\mathbb Z/N\mathbb Z$. The resulting $N$ embedded copies partition the edges of $K_N$. Indeed unordered pairs have difference classes $\{d,-d\}$ with $1\le d\le m$. For each class the original tree has exactly one edge. Translating that edge produces every pair in its class exactly once: a nonzero translation fixing an unordered pair would swap its endpoints and have order two, impossible in a group of odd order. Different classes cannot overlap. The total $Nm=\binom N2$ also matches. This proves a consequence of graceful labelling; a decomposition obtained by a different method need not provide the particular labels required here.

Why appending one new label is not an induction.

Start with a graceful labelling using $0,\ldots,m$ and attach a leaf at a vertex labelled $x$. If old labels are frozen, the only unused label in the new interval is $m+1$. The only missing edge difference is also $m+1$, so the new edge works exactly when $x=0$. Complementing all old labels interchanges zero and $m$ but does not put an arbitrary prescribed vertex at zero. For example, the path labelled $0,2,1$ is graceful, but attaching a leaf at the endpoint labelled one and assigning it three repeats difference two. The new path does have a graceful labelling, $0,3,1,2$, after a global change. Thus this is an obstruction to a frozen labelling algorithm, not a counterexample tree.

Verification and final status.

The root batch script checks path labels through forty edges and every double-star with $0\le a,b\le12$, comparing both the vertex-label and edge-difference sets exactly. It also checks the complete-graph cyclic decompositions for the first twelve paths and the failed leaf extension. Those computations test formulas; the proofs above establish the infinite families. UNRESOLVED. Arbitrary trees require a mechanism for coordinated relabelling after adding branches. Assuming that a graceful labelling can always put a prescribed attachment vertex at zero would introduce an additional unproved assertion rather than complete induction.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3212 (OPG-439), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Graceful Tree Conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/graceful_tree_conjecture.
• R1 Matthew Superdock, The Graceful Tree Conjecture: a class of graceful diameter-6 trees, arXiv:1403.1564. Primary source checked 1 October 2026. https://arxiv.org/abs/1403.1564.

The Graceful Tree Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A tree is a finite connected graph with no cycle. If it has $m$ edges, it has $m+1$ vertices. A graceful labelling is a bijection $f:V(T)\to\{0,\ldots,m\}$ for which the multiset $\{|f(u)-f(v)|:uv\in E(T)\}$ is exactly $\{1,\ldots,m\}$. Both the vertex labels and the induced edge differences are required to be distinct. [S1] [S2]

Statement recorded in the supplied source.

Every tree can be gracefully labeled: vertices can be assigned distinct labels from $\{0, 1, \ldots, |E|\}$ such that edge labels (absolute differences) are all distinct. [S1]

Short English statement

Can every finite tree be numbered so that its edge differences use each positive integer up to the number of edges exactly once?

Research attempt

Status: UNRESOLVED. We construct graceful labelings for paths and double stars, prove an extension criterion with a prescribed zero label, and exhibit the obstruction to turning that criterion into an induction for all trees. We also derive an exact finite search formulation and a parity check for any proposed labeling. No new general solution or new family theorem is claimed.

Source check and strategy.

The inherited web formulation [S2] returned a 404 response when consulted on 1 October 2026. Gallian's primary survey [E1] gives an accessible reference for graceful graph labeling; only its framework is used here. We preserve the canonical statement. The proof attempt is constructive: arrange edge differences consecutively, then test whether a leaf can always be inserted into a graceful labeling of a smaller tree.

Paths: an explicit alternating construction.

Let $v_0,\ldots,v_m$ be the vertices in path order. Define \[ f(v_{2j})=j,\qquad f(v_{2j+1})=m-j \] whenever the subscripts lie between zero and $m$. The even-position labels increase from zero and the odd-position labels decrease from $m$. They form disjoint intervals whose union is $\{0,\ldots,m\}$, so $f$ is bijective. The edge from position $2j$ to $2j+1$ has difference $m-2j$; the next edge has difference $m-2j-1$. In path order the edge differences are therefore $m,m-1,\ldots,1$.

This includes $m=0$, where the single vertex receives zero and the edge condition is empty. It also places zero at one end of every path. The formula supplies a chosen labeling, not a license to put zero at an arbitrary prescribed vertex by an arbitrary permutation of labels.

Double stars: a second complete family.

A double star has adjacent centres $u,v$, with $a$ leaves at $u$ and $b$ leaves at $v$, hence $m=a+b+1$ edges. Give $u$ label zero and $v$ label $b+1$. Give the $b$ leaves at $v$ the labels $1,\ldots,b$, and the $a$ leaves at $u$ the labels $b+2,\ldots,m$. These labels partition $\{0,\ldots,m\}$. The $v$-leaf differences are $1,\ldots,b$, the central difference is $b+1$, and the $u$-leaf differences are $b+2,\ldots,m$. Every desired difference occurs once.

When $a$ or $b$ is zero, the corresponding interval is empty and the same proof applies. The construction consequently contains stars and the single edge without additional exceptions. It relies on the two-level incidence pattern; when an attached branch has its own branches, assigning a consecutive interval at one centre no longer controls all internal differences.

The exact leaf-extension lemma.

Suppose a tree $T$ has $m$ edges and a graceful labeling $f$ with $f(v)=0$. Attach a new leaf $w$ to $v$ and put $f(w)=m+1$, leaving old labels unchanged. The old edge differences remain $1,\ldots,m$, and the new edge has difference $m+1$. This proves gracefulness of the enlarged tree.

Conversely, if an extension leaves every old label unchanged and uses the only unused label $m+1$ on $w$, it is graceful only if $f(v)=0$: the old differences already exhaust $1,\ldots,m$, so the new difference must be $m+1$, forcing $|(m+1)-f(v)|=m+1$. Since $0\le f(v)\le m$, this is equivalent to $f(v)=0$.

Complementation $f\mapsto m-f$ preserves every difference and exchanges labels zero and $m$. It does not allow an arbitrary vertex to become zero. Similarly, permuting labels arbitrarily does not preserve edge differences. Thus induction by deleting a leaf requires a stronger rooted assertion at its attachment vertex, not merely the ordinary induction hypothesis that the smaller tree is graceful.

A failed extension of a specific graceful labeling.

Take the three-vertex path $a-b-c$ with labels $(0,2,1)$. Its differences are two and one, so it is graceful. Attach a new leaf $w$ to $c$. Keeping the old labels and assigning three to $w$ creates difference two again; the required difference three is absent. Complementing the old labeling gives $(2,0,1)$ and still leaves label one at $c$, so this second unchanged-label extension also fails.

The enlarged tree is a four-vertex path and is graceful, for instance with labels $(0,3,1,2)$ in the order $a,b,c,w$. Thus the failure is not a counterexample to the conjecture; it proves that a successful induction may need to change multiple old labels. The usual induction hypothesis provides some graceful labeling, without the additional root condition needed by the extension lemma. We have not established a general theorem supplying that condition or a universally valid relabeling operation.

A useful certificate identity.

For any graceful labeling, \[ \sum_{uv\in E(T)}|f(u)-f(v)|=\frac{m(m+1)}2. \] Reducing modulo two and using $|r-s|\equiv r+s\pmod2$ yields \[ \sum_{v\in V(T)}\deg(v)f(v)\equiv \frac{m(m+1)}2\pmod2. \] Only odd-degree vertices contribute on the left. This is a necessary checksum for a candidate. It is not sufficient: repeated differences can have the correct sum or parity. A sound verifier must test bijectivity of vertex labels and equality of the entire edge-difference multiset to $\{1,\ldots,m\}$.

Finite search and final gap.

One exact formulation has integer variables $x_v\in\{0,\ldots,m\}$, pairwise distinct, and edge variables $y_{uv}=|x_u-x_v|\in\{1,\ldots,m\}$, also pairwise distinct. Since the numbers of variables match their allowed label sets, these constraints are equivalent to gracefulness. Enumerating vertex permutations is complete but factorial in $m+1$. Complementation permits a symmetry restriction on one fixed edge, such as $x_u<x_v$, without losing all representatives; prescribing a root label zero lacks that justification.

The constructions and identities above were checked algebraically, with no claimed exhaustive enumeration. The exact unresolved step is a labeling construction for every tree, or a replacement extension lemma that can relabel an existing tree while maintaining all old differences. The family formulas provide positive test cases for such a method. A finite search finding labelings for small trees would not prove that an arbitrary attachment vertex can always meet the induction requirement.

Sources

• E1 J. A. Gallian, A Dynamic Survey of Graph Labeling, 27th edition, 15 November 2024. Source consulted 1 October 2026. https://www.combinatorics.org/files/Surveys/ds6/ds6v27-2024.pdf.

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 31 (GT-003), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Graceful Tree Conjecture, Graph-theory open problems tracker. https://mlelarge.github.io/graph-conjectures/op/graceful_tree_conjecture/. Bibliographic information from the supplied record.