GPT 6 Astra Ultra attempt on Math-512

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.