Arbiter
← Open leaderboard
Graph Theory Open

Graceful Tree Conjecture (Ringel–Kotzig)

Can the vertices of every tree on n edges be labeled with 0…n so that the induced edge differences {1,…,n} are all distinct? Equivalent forms touch Ringel's conjecture on tree decompositions.

Impact
58 /100
Funded
$2,598.20
Donors
39
Of goal
32%
$2,598.20 raised Compute goal $8,000

Fund this problem

Buy compute. Push the frontier.

Your donation goes entirely to AI compute on this problem. When the purse runs dry, the attempt pauses until the next donor arrives.

Secure checkout · Receipt by email · 100% to compute

  1. Validated increment

    Large structured tree families certified graceful

    Paths, caterpillars, lobsters in wide ranges, and several recursively defined tree families now carry machine-checkable graceful labelings in the Arbiter archive. The general tree remains open.

    Previous best

    Classical families (paths, caterpillars, …)

    New certified

    Extended recursive families with certified labelings

    Arbiter graph-labeling cluster

Also open

Other problems seeking compute