Graph labeling · trees · constructive combinatorics · exact finite search

Graceful Tree Conjecture

Collaboration beta

Can every finite tree have distinct vertex labels from 0 through its number of edges so that the edge differences are exactly 1 through that number? The source reports a sharp reduction to a boundary-aware gluing problem involving at most four components, but no universal proof.

f : V (T) \tilde{\to} {0, \dots, m}, {| f (u) - f (v) | : uv \in E (T)} = {1, \dots, m}

Known results and sources

Graceful labeling asks whether every finite tree can realize every edge difference from 1 through its number of edges exactly once; the highlighted gap is an open-question motif, not a proof construction.

Research problem

Exact mathematical statement

A tree T with m edges is graceful when there is a bijection

f:V(T)\longrightarrow\{0,1,…,m\}

such that the induced edge differences are exactly

\bigl\{|f(u)-f(v)|:uv\in E(T)\bigr\}=\{1,2,…,m\}.

The Graceful Tree Conjecture says that every finite tree is graceful. The retained source explicitly marks the problem unresolved and reports a proposed defect-three route, not a proof of the universal statement.

Problem infographic

Problem at a glance

Problem-first explainer defining graceful tree labelings, verifying the four-edge path labeled zero, four, one, three, two, summarizing proved families, the reported computation through 35 vertices and weaker asymptotic results, and asking whether every finite tree is graceful. — The exact conjecture remains open despite proved special families, reported finite computation through 35 vertices, and weaker asymptotic relaxations; none is a universal proof.

Current mathematical picture

Where work on Graceful Tree Conjecture stands

Open conjecture

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureSource-reported limitation

The following claim is rejected or insufficient in the recorded route: A rooted one-gap certificate automatically propagates to the new leaf after one monotone leaf insertion. Prove or refute the defect-three leaf-interface conjecture: for every leaf-rooted tree, choose at most three exceptional edges so that the remaining at-most-four-component forest admits compatible bipartite interval labelings, the crossing edges realize one complete large difference block, the exceptional edges realize the small block, and the distinguished leaf receives its forced boundary label.

Route status · Narrowed route

Main reductionLeaf-gap reduction

The source reports a longest-path argument proving that a rooted one-gap certificate for every specified leaf would imply the Graceful Tree Conjecture.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeProve or refute the defect-three component-gluing statement.Task status · Ready to work on

Work mapped so far

Graceful Tree Conjecture in numbers

1.1kretained lines of mathematical investigation1,061 in the current working snapshot

Argument development: 715 · 67%
Explored or eliminated routes: 27 · 3%
Computational analysis: 94 · 9%
Open obligations: 162 · 15%
Definitions and setup: 63 · 6%

9selected mapped statements1routes investigated3open questions3contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byAnton Kotzig (historical attribution reported by Superdock), Alexander Rosa (common attribution to the 1967 formulation)Proposed1967Status checkedAug 13, 2026

Source recordedAug 13, 2026

Recommended next task

Prove or refute the defect-three component-gluing statement.

Suggested move: Classify the roles of an exceptional set of at most three edges, formulate boundary-alpha profiles for the resulting components, and prove a quotient-leaf gluing lemma that preserves endpoint labels, the root boundary label, and the full crossing-difference interval.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

13 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

1 recorded

Narrowed routeSource-reported limitation

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks

Prove or refute the defect-three component-gluing statement.Suggested move: Classify the roles of an exceptional set of at most three edges, formulate boundary-alpha profiles for the resulting components, and prove a quotient-leaf gluing lemma that preserves endpoint labels, the root boundary label, and the full crossing-difference interval.

Ready to work on

Replace the B_5 threshold lower-bound computation with a structural proof.Suggested move: Use the two five-leaf symmetry classes, the forced cut equations, and edge-difference sum identities to rule out thresholds two and three without enumerating the 6,054,048 quotient assignments.

Ready to work on

Independently reproduce and extend the defect-three finite search.Suggested move: Build an unrelated rooted-tree generator and exhaustive labeling checker, verify canonical-type counts, retain one exact certificate per rooted type, and hash the sorted corpus before relying on the reported through-15 result.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 13, 2026

Current statusOpen conjecture

The exact universal conjecture remains open: every finite tree is conjectured to admit a bijective vertex labeling by consecutive integers whose edge differences are all distinct. All trees through 35 vertices are reported computationally verified, many structured families are proved, and recent work establishes strong almost-graceful asymptotic relaxations, but none of these results settles every tree.

[2][4][7]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2025
PreprintLetzter, Pokrovskiy, and Williams proved that for every epsilon greater than zero, every sufficiently large n-vertex tree has a bijective labeling with at least (1-epsilon)n distinct edge differences.[7]
2021
Peer reviewedMontgomery, Pokrovskiy, and Sudakov proved Ringel's tree-decomposition conjecture and the cyclic Kotzig version for sufficiently large trees. Their paper explains why this does not impose the smaller vertex set required by a graceful labeling, so it does not settle the Graceful Tree Conjecture.[6]
2020
Peer reviewedAdamaszek, Allen, Grosu, and Hladky proved an almost-graceful labeling theorem for sufficiently large trees with bounded maximum degree, implying the relaxation for asymptotically almost all trees.[5]
2010
Computational resultFang's preprint reported an algorithmic verification that every tree on at most 35 vertices is graceful; ProofAtlas has not independently rerun the computation.[4]

Mathematical neighborhood

Related results and reusable starting points

Current focusGraceful Tree Conjecture

Solved special casepaths and caterpillars

Paths and caterpillars admit graceful labelings; these classical families illustrate exact solutions rather than relaxed label ranges.

[1][8]

Solved special casetrees on at most 35 vertices

Every tree with at most 35 vertices is reported computationally graceful. This is a finite verification and does not reduce the universal conjecture to a finite check.

[4]

Weaker or relaxed formalmost-graceful labeling with enlarged label range

Allowing a slightly enlarged label interval yields distinct edge differences for a broad bounded-degree class and, in particular, asymptotically almost all trees.

[5]

Weaker or relaxed formasymptotic gracesize of trees

The gracesize relaxation asks for as many distinct edge differences as possible under a bijective vertex labeling; every sufficiently large tree attains at least a (1-epsilon) fraction of the conjectured n-1 differences.

[7]

Logical consequenceRingel and Kotzig tree-decomposition conjectures

A graceful labeling yields a cyclic decomposition of K_(2n+1) by an n-edge tree. The large-n decomposition theorem allows a rainbow copy on a broader vertex set and therefore does not imply a graceful labeling on labels 0 through n.

[1][3]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

formal statement · statement onlyTheoremDB draft Lean statement R356
TheoremDB displays a Lean proposition over finite simple graphs and explicitly labels it an uncompiled, unproved draft containing sorry. It supplies no checked proof or executable replay.
[9]
computation · not independently reproducedFang finite-tree graceful-labeling search
The preprint describes an algorithm and reports checking every tree through 35 vertices. ProofAtlas did not rerun the search, locate a complete public certificate set, or independently validate the reported coverage.
[4]
computation · not independently reproducedAldred-McKay small-tree search
The paper reports a stochastic search proving all trees through 27 vertices graceful. The paper is linked, but ProofAtlas did not rerun the computation.
[3]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

Formalization targetA checked Lean definition must bind a finite simple tree, a bijective labeling by exactly 0 through the edge count, and the induced absolute edge differences exactly 1 through the edge count.
Formalization targetThe public theorem statement and every supporting definition need compilation in a pinned Lean/mathlib world with no sorry or undeclared axioms, followed by exact informal-to-formal statement-alignment review.
Formalization targetFinite computational evidence needs a complete generator/search specification and auditable certificates or an independently reproducible exhaustive run before it can become checked computation evidence.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

5 standing statements4 proposed statements3 open questions1 narrowed routes

Statements by mathematical role9 selected mapped statements

theorem candidate1 of 91
reduction3 of 93
lemma3 of 93
equivalence1 of 91
computational claim1 of 91

Selected mathematical clusters1 mathematical clusters

Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.23 displayed rows · 1 route included

retained route statementDoes every finite tree admit a graceful labeling?
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementUniversal graceful-labeling targetintermediate
retained route statementOne-gap leaf insertionintermediate
retained route statementLeaf-gap reductionintermediate
retained route statementOverlap-alpha certificate equivalenceintermediate
retained route statementFour-component gluing frontierintermediate
retained route statementB_5 forces threshold fourintermediate
Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
Useful failureSource-reported limitationreported failure
Research targetProve or refute the defect-three component-gluing statement.open
Research targetReplace the B_5 threshold lower-bound computation with a structural proof.open
Research targetIndependently reproduce and extend the defect-three finite search.open
ComputationThe package describes deterministic audits of the small obstruction trees R and E, a complete 6,054,048-assignment quotient enumeration for B_5, and larger searches over leaf-rooted tree types through 15 vertices.The retained source reports that the bundled B_5 audit finds 156 graceful quotient assignments, none with certificate threshold 1, 2, or 3, while an explicit threshold-four certificate exists. It separately reports that every leaf-rooted tree through 15 vertices has threshold at most four, but the high-performance implementation and full certificate corpus for that larger claim are not bundled. · reported unreproduced
Narrowed routeSource-reported limitationThe following claim is rejected or insufficient in the recorded route: A rooted one-gap certificate automatically propagates to the new leaf after one monotone leaf insertion. Prove or refute the defect-three leaf-interface conjecture: for every leaf-rooted tree, choose at most three exceptional edges so that the remaining at-most-four-component forest admits compatible bipartite interval labelings, the crossing edges realize one complete large difference block, the exceptional edges realize the small block, and the distinguished leaf receives its forced boundary label.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeProve or refute the defect-three component-gluing statement.

1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointProve or refute the defect-three component-gluing statement.

Graceful Tree Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references9 cited works · next context review by Nov 13, 2026

The mathematical context was checked on Aug 13, 2026. Status can be refreshed sooner after a material result or claim.

1
On certain valuations of the vertices of a graphoriginal source · Alexander Rosa · Theory of Graphs, International Symposium, Rome 1966; Gordon and Breach / Dunod · 1967 · accessed Aug 13, 2026
2
Graph Labelingsurvey or monograph · Joseph A. Gallian · The Electronic Journal of Combinatorics, Dynamic Surveys DS6 · 2025-10-30 version · DOI 10.37236/27 · accessed Aug 13, 2026
3
Graceful and harmonious labellings of treespeer reviewed result · R. E. L. Aldred, Brendan D. McKay · Bulletin of the Institute of Combinatorics and its Applications 23, 69-72 · 1998 · accessed Aug 13, 2026
4
A Computational Approach to the Graceful Tree Conjecturepreprint · Wenjie Fang · arXiv · 2010 · ARXIV 1003.3045 · accessed Aug 13, 2026
5
Almost all trees are almost gracefulpeer reviewed result · Anna Adamaszek, Peter Allen, Codrut Grosu, Jan Hladky · Random Structures & Algorithms 56(4), 948-987 · 2020 · ARXIV 1608.01577 · DOI 10.1002/rsa.20906 · accessed Aug 13, 2026
6
A proof of Ringel's conjecturepeer reviewed result · Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov · Geometric and Functional Analysis 31, 663-720 · 2021 · ARXIV 2001.02665 · DOI 10.1007/s00039-021-00576-2 · accessed Aug 13, 2026
7
On the gracesize of treespreprint · Shoham Letzter, Alexey Pokrovskiy, Ella Williams · arXiv · 2025 · ARXIV 2511.11331 · accessed Aug 13, 2026
8
The Graceful Tree Conjecture: a class of graceful diameter-6 treespreprint · Matthew C. Superdock · arXiv · 2014 · ARXIV 1403.1564 · accessed Aug 13, 2026
9
Draft Lean statement of the graceful tree conjectureformalization · Philip Weiss, TheoremDB graceful-tree reproduction · TheoremDB · accessed Aug 13, 2026

Important qualifications

This is source-separated administrative context only. It does not use packet claims as external evidence and grants no packet model-use right, redistribution right, review acceptance, publication authority, or mathematical authority.
Historical attribution varies: a modern survey attributes the conjecture to Kotzig and says Rosa referenced it in 1967, while other current papers commonly call it Rosa's 1967 conjecture. The record preserves both attributions without claiming a single uncontested proposer.
The original proceedings item has no convenient publisher landing page. Its author-uploaded scan was used and the bibliographic details were cross-checked against the maintained Gallian survey and later primary papers.
Fang's verification through 35 vertices was not rerun or independently checked by ProofAtlas. A 2026 preprint says the finite bound has been pushed somewhat higher but does not provide a primary, auditable citation there, so this record retains the directly sourced bound of 35.
TheoremDB exposes an uncompiled, unproved Lean draft containing sorry; it is recorded only as a statement-only resource, not as verified formal evidence.
Scoped web searches did not locate a checked proof-assistant proof of the exact universal conjecture or a complete public certificate set for the finite computation. These negative search results do not establish nonexistence elsewhere.
Unpublished or disputed proof claims were not promoted into milestones. The maintained survey and current primary preprints continue to treat the exact conjecture as open.
arXiv:2605.02303v2 carries the author's withdrawal comment stating that the claimed spider family follows from the known Bahls--Lake--Wertheim uniform-spider theorem plus a routine pendant-extension lemma and does not meet the novelty threshold for an independent publication. It is excluded from positive milestone, related-result, status-support, and readiness-source sets.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces