Introduction

A tree is a connected network with no cycles: nn dots (vertices) joined by exactly n−1n-1 lines (edges). Now play a numbering game. Write the numbers 0,1,…,n−10, 1, \dots, n-1 on the vertices, each number used once. Every edge then gets its own label: the difference ∣a−b∣|a-b| between the numbers at its two ends.

The labelling is graceful if those n−1n-1 edge labels are exactly 1,2,…,n−11, 2, \dots, n-1 — every difference appears once, none is missing, none repeats. Because there are exactly n−1n-1 edges and n−1n-1 possible differences, "all different" and "all present" mean the same thing.

Some trees are easy. For a star (one centre touching every other vertex) put 00 in the middle and 1,…,n−11, \dots, n-1 on the tips. For a path zig-zag between the ends of the range: 0,n−1,1,n−2,2,…0, n-1, 1, n-2, 2, \dots — the differences come out as n−1,n−2,n−3,…,1n-1, n-2, n-3, \dots, 1. Checking any proposed labelling is a few lines of code:

function isGraceful(tree, label):        // label[v] in 0..n-1, all distinct
    seen = empty set
    for each edge (u, v) in tree.edges:
        d = |label[u] - label[v]|
        if d == 0 or d in seen: return false
        add d to seen
    return true                             // n-1 distinct values in 1..n-1

The Graceful Tree Conjecture (also called the Ringel–Kotzig conjecture) claims that every tree, no matter how branchy or lopsided, has a graceful labelling. It grew out of a 1963 question by Gerhard Ringel and a 1964 strengthening by Anton Kotzig; in 1967 Alexander Rosa introduced these labellings under the name β-valuations, and Solomon Golomb gave them the name "graceful" in 1972. Computers have checked every tree with up to 35 vertices. Not one fails. Yet, sixty years on, nobody has found a proof.

Label It Yourself

Choose a tree — a path, a star, a caterpillar or a random one — or switch on Add leaves and grow your own by tapping vertices. Then tap a vertex and a number to label it. Each edge shows its difference: the strip of needed differences turns green when a value is used once and red when two edges collide.

<p class="hint">Give every vertex a different number from 0 to n−1. Each edge shows the difference of its two ends. The labelling is <b>graceful</b> when the edge differences are exactly 1, 2, …, n−1 — each once. Tap a vertex, then a number.</p>
<div class="row presets">
  <button type="button" class="ghost" data-preset="path">Path</button>
  <button type="button" class="ghost" data-preset="star">Star</button>
  <button type="button" class="ghost" data-preset="cat">Caterpillar</button>
  <button type="button" class="ghost" data-preset="random">Random tree</button>
</div>
<svg id="tree" viewBox="0 0 340 240" role="img" aria-label="The tree being labelled; tap a vertex to select it."></svg>
<div class="cap">Edge differences needed (green = used once, red = repeated)</div>
<div class="diffs" id="diffs"></div>
<div class="cap">Labels (tap to assign to the selected vertex)</div>
<div class="chips" id="chips"></div>
<div class="status" id="status" aria-live="polite"></div>
<div class="row">
  <button type="button" id="leaf" class="ghost">Add leaves: off</button>
  <button type="button" id="solve">Solve</button>
  <button type="button" id="clear" class="ghost">Clear labels</button>
  <button type="button" id="stress">Stress test 300 trees</button>
</div>

/* Colours as variables so the dark theme only has to swap values. */
:root { --fg: #1f2933; --muted: #52606d; --line: #9aa8b6; --panel: #eef2f6; --accent: #1d3557;
        --node: #ffffff; --ok: #0a7d33; --okbg: #d8f3e2; --bad: #c92f3c; --badbg: #fde2e4; --sel: #f4a261; }
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); margin: 0; background: #ffffff; }
.hint { font-size: .88rem; color: var(--muted); margin: 0 0 .6rem; line-height: 1.45; }
.row { display: flex; gap: .4rem; flex-wrap: wrap; margin: .35rem 0; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .75rem; border: 1px solid var(--accent);
         background: var(--accent); color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--accent); }
button.on { background: var(--sel); border-color: var(--sel); color: #1f2933; }
button:disabled { opacity: .45; cursor: default; }
svg#tree { width: 100%; max-width: 460px; height: auto; display: block; background: var(--panel);
           border-radius: 10px; margin: .3rem 0; touch-action: manipulation; }
.edge { stroke: var(--line); stroke-width: 2.2; }
.edge.dup { stroke: var(--bad); }
.vtx circle { fill: var(--node); stroke: var(--accent); stroke-width: 2; cursor: pointer; }
.vtx.lab circle { fill: var(--okbg); }
.vtx.sel circle { stroke: var(--sel); stroke-width: 3.5; }
.vtx text { font: 700 12px ui-monospace, monospace; fill: var(--fg); text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.elab rect { fill: var(--panel); }
.elab text { font: 700 10px ui-monospace, monospace; fill: var(--ok); text-anchor: middle; dominant-baseline: central; }
.elab.dup text { fill: var(--bad); }
.cap { font-size: .75rem; color: var(--muted); margin-top: .35rem; text-transform: uppercase; letter-spacing: .04em; }
.diffs, .chips { display: flex; flex-wrap: wrap; gap: 3px; margin: .2rem 0; }
.d { min-width: 24px; height: 22px; padding: 0 3px; display: flex; align-items: center; justify-content: center;
     font: 700 11px ui-monospace, monospace; border-radius: 5px; border: 1px dashed var(--line); color: var(--muted); }
.d.hit { background: var(--okbg); border: 1px solid var(--ok); color: var(--ok); }
.d.dup { background: var(--badbg); border: 1px solid var(--bad); color: var(--bad); }
.chip { min-width: 30px; padding: .3rem .2rem; font: 700 13px ui-monospace, monospace; }
.chip.used { opacity: .4; }
.chip.mine { opacity: 1; background: var(--sel); border-color: var(--sel); color: #1f2933; }
.status { font-size: .92rem; font-weight: 600; margin: .45rem 0; min-height: 2.6em; line-height: 1.35; }
.status.ok { color: var(--ok); }
.status.bad { color: var(--bad); }
@media (prefers-color-scheme: dark) {
  :root { --fg: #e4e9ef; --muted: #a3b1bf; --line: #5b6878; --panel: #1b222b; --accent: #9fb2c8;
          --node: #12171d; --ok: #5fd08a; --okbg: #17382a; --bad: #ff7b86; --badbg: #3d1d22; --sel: #f4a261; }
  body { background: #12171d; }
  button { color: #12171d; }
  button.ghost { background: transparent; color: var(--accent); }
}

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// State: the tree (n vertices, edge list), the labels (-1 = empty) and the selected vertex.
const MAXN = 16, W = 340, H = 240, NS = 'http://www.w3.org/2000/svg';
let n = 0, edges = [], adj = [], lab = [], sel = -1, addMode = false, busy = false, msg = null;
const $ = (id) => document.getElementById(id);

function buildAdj() {
  adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
}
function setTree(N, E, L) {
  n = N; edges = E.map((e) => e.slice()); buildAdj();
  lab = L ? L.slice() : new Array(n).fill(-1); sel = -1;
}

// A uniformly random labelled tree, decoded from a random Prüfer sequence.
function randomTree(N) {
  if (N < 2) return [];
  const P = []; for (let i = 0; i < N - 2; i++) P.push(Math.floor(Math.random() * N));
  const deg = new Array(N).fill(1); for (const x of P) deg[x]++;
  const E = [];
  for (const x of P) { for (let j = 0; j < N; j++) { if (deg[j] === 1) { E.push([j, x]); deg[j]--; deg[x]--; break; } } }
  const r = []; for (let j = 0; j < N; j++) if (deg[j] === 1) r.push(j);
  E.push([r[0], r[1]]);
  return E;
}
// The preset trees. Each entry returns [number of vertices, edge list].
const PRESETS = {
  path: () => [7, [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]]],
  star: () => [7, [[0,1],[0,2],[0,3],[0,4],[0,5],[0,6]]],
  cat: () => [10, [[0,1],[1,2],[2,3],[0,4],[1,5],[1,6],[2,7],[3,8],[3,9]]],
  random: () => { const N = 6 + Math.floor(Math.random() * 5); return [N, randomTree(N)]; }
};

// Backtracking by differences: the largest difference m must join labels 0 and m,
// then m−1 joins 0 and m−1 or 1 and m, and so on downwards. Each step places the
// next missing difference on some edge; nodes counts every placement we try.
function solve(N, E, budget) {
  const m = E.length;
  const A = Array.from({ length: N }, () => []); for (const [a, b] of E) { A[a].push(b); A[b].push(a); }
  const L = new Array(N).fill(-1), owner = new Array(m + 1).fill(-1), usedD = new Array(m + 1).fill(false);
  let nodes = 0, aborted = false;
  function put(v, l) {
    const ds = [];
    for (const w of A[v]) { if (L[w] < 0) continue; const d = Math.abs(l - L[w]);
      if (d === 0 || usedD[d] || ds.includes(d)) return null; ds.push(d); }
    L[v] = l; owner[l] = v; for (const d of ds) usedD[d] = true; return ds;
  }
  function undo(v, ds) { owner[L[v]] = -1; L[v] = -1; for (const d of ds) usedD[d] = false; }
  function rec(d) {
    while (d > 0 && usedD[d]) d--;
    if (d === 0) return true;
    // Case 1: the difference grows out of a vertex that already has a label.
    for (let x = 0; x + d <= m; x++) {
      const y = x + d;
      for (const [have, want] of [[x, y], [y, x]]) {
        if (owner[have] < 0 || owner[want] >= 0) continue;
        for (const v of A[owner[have]]) { if (L[v] >= 0) continue;
          if (nodes >= budget) { aborted = true; return false; } nodes++;
          const ds = put(v, want); if (!ds) continue;
          if (rec(d - 1)) return true; undo(v, ds); if (aborted) return false; }
      }
    }
    // Case 2: the difference sits on an edge whose two ends are both still empty.
    for (let x = 0; x + d <= m; x++) {
      const y = x + d; if (owner[x] >= 0 || owner[y] >= 0) continue;
      for (const [a, b] of E) { if (L[a] >= 0 || L[b] >= 0) continue;
        for (const [p, q] of [[a, b], [b, a]]) {
          if (nodes >= budget) { aborted = true; return false; } nodes++;
          const d1 = put(p, x); if (!d1) continue;
          const d2 = put(q, y); if (!d2) { undo(p, d1); continue; }
          if (rec(d - 1)) return true; undo(q, d2); undo(p, d1); if (aborted) return false; }
      }
    }
    return false;
  }
  if (N === 1) return { labels: [0], nodes: 1, aborted: false };
  const found = rec(m);
  return { labels: found ? L.slice() : null, nodes, aborted };
}
// Independent check: distinct labels and n−1 distinct non-zero edge differences.
function isGraceful(N, E, L) {
  if (!L || new Set(L).size !== N || L.some((x) => x < 0 || x > E.length)) return false;
  const D = new Set(E.map(([a, b]) => Math.abs(L[a] - L[b])));
  return D.size === E.length && !D.has(0);
}

// Layout: root the tree at a centre vertex, then place leaves left to right by depth.
function bfs(src) {
  const d = new Array(n).fill(-1), par = new Array(n).fill(-1); d[src] = 0; const q = [src];
  while (q.length) { const v = q.shift(); for (const w of adj[v]) if (d[w] < 0) { d[w] = d[v] + 1; par[w] = v; q.push(w); } }
  return { d, par };
}
function layout() {
  let root = 0, best = Infinity;
  for (let v = 0; v < n; v++) { const e = Math.max(...bfs(v).d); if (e < best) { best = e; root = v; } }
  const { d, par } = bfs(root);
  const kids = Array.from({ length: n }, () => []);
  for (let v = 0; v < n; v++) if (par[v] >= 0) kids[par[v]].push(v);
  const xs = new Array(n); let leaf = 0;
  (function place(v) {
    if (!kids[v].length) { xs[v] = leaf++; return; }
    kids[v].forEach(place); xs[v] = (xs[kids[v][0]] + xs[kids[v][kids[v].length - 1]]) / 2;
  })(root);
  const maxD = Math.max(...d);
  return xs.map((x, v) => ({ x: leaf > 1 ? 22 + x * (W - 44) / (leaf - 1) : W / 2,
                             y: maxD ? 24 + d[v] * (H - 48) / maxD : H / 2 }));
}
function el(tag, attrs, parent) {
  const e = document.createElementNS(NS, tag);
  for (const k in attrs) e.setAttribute(k, attrs[k]);
  parent.appendChild(e); return e;
}
function diffCounts() {
  const c = new Array(Math.max(n, 1)).fill(0);
  for (const [a, b] of edges) if (lab[a] >= 0 && lab[b] >= 0) c[Math.abs(lab[a] - lab[b])]++;
  return c;
}

function draw() {
  const svg = $('tree'); svg.innerHTML = '';
  const P = layout(), R = n > 11 ? 10 : 13, cnt = diffCounts();
  for (const [a, b] of edges) {
    const dd = (lab[a] >= 0 && lab[b] >= 0) ? Math.abs(lab[a] - lab[b]) : 0;
    el('line', { x1: P[a].x, y1: P[a].y, x2: P[b].x, y2: P[b].y, class: 'edge' + (dd && cnt[dd] > 1 ? ' dup' : '') }, svg);
  }
  for (const [a, b] of edges) {
    if (lab[a] < 0 || lab[b] < 0) continue;
    const dd = Math.abs(lab[a] - lab[b]);
    const g = el('g', { class: 'elab' + (cnt[dd] > 1 ? ' dup' : '') }, svg);
    const mx = (P[a].x + P[b].x) / 2, my = (P[a].y + P[b].y) / 2;
    el('rect', { x: mx - 9, y: my - 7, width: 18, height: 14, rx: 4 }, g);
    el('text', { x: mx, y: my }, g).textContent = dd;
  }
  for (let v = 0; v < n; v++) {
    const g = el('g', { class: 'vtx' + (lab[v] >= 0 ? ' lab' : '') + (v === sel ? ' sel' : '') }, svg);
    el('circle', { cx: P[v].x, cy: P[v].y, r: R }, g);
    el('text', { x: P[v].x, y: P[v].y }, g).textContent = lab[v] >= 0 ? lab[v] : '';
    g.addEventListener('click', () => tapVertex(v));
  }
  const db = $('diffs'); db.innerHTML = '';
  for (let d = 1; d < n; d++) {
    const s = document.createElement('div');
    s.className = 'd' + (cnt[d] === 1 ? ' hit' : cnt[d] > 1 ? ' dup' : '');
    s.textContent = d; db.appendChild(s);
  }
  const cb = $('chips'); cb.innerHTML = '';
  for (let l = 0; l < n; l++) {
    const b = document.createElement('button'); b.type = 'button';
    b.className = 'chip' + (lab.includes(l) ? ' used' : '') + (sel >= 0 && lab[sel] === l ? ' mine' : '');
    b.textContent = l; b.disabled = busy;
    b.addEventListener('click', () => pick(l)); cb.appendChild(b);
  }
  status(cnt);
}
function setStatus(t, cls) { const s = $('status'); s.textContent = t; s.className = 'status ' + cls; }
function status(cnt) {
  if (msg) { setStatus(msg.t, msg.cls); return; }
  const m = n - 1, fixed = edges.filter(([a, b]) => lab[a] >= 0 && lab[b] >= 0).length;
  const dup = cnt.findIndex((x, i) => i > 0 && x > 1);
  if (dup > 0) setStatus(i18nFmt("Difference %d% appears on more than one edge (red). Every difference may appear only once.", { d: dup }), 'bad');
  else if (fixed === m && lab.every((x) => x >= 0)) setStatus(i18nFmt("✓ Graceful! The differences are exactly 1 to %m%, each used once.", { m }), 'ok');
  else if (fixed === 0) setStatus("Tap a vertex, then tap a number to label it.", '');
  else setStatus(i18nFmt("%k% of %m% edge differences fixed — no repeats so far.", { k: fixed, m }), '');
}

function tapVertex(v) {
  if (busy) return;
  if (addMode) {
    if (n >= MAXN) { msg = { t: i18nFmt("This demo stops at %max% vertices — the search stays instant up to there.", { max: MAXN }), cls: 'bad' }; draw(); return; }
    edges.push([v, n]); lab.push(-1); n++; buildAdj(); msg = { t: "Tap any vertex to hang a new leaf on it. Turn the mode off to label.", cls: '' }; draw(); return;
  }
  sel = v; msg = null; draw();
}
function pick(l) {
  if (busy) return;
  if (sel < 0) { msg = { t: "Select a vertex first, then tap a number.", cls: '' }; draw(); return; }
  msg = null; const o = lab.indexOf(l);
  if (o === sel) { lab[sel] = -1; draw(); return; }
  if (o >= 0) lab[o] = lab[sel];
  lab[sel] = l;
  // Jump to the next vertex that still has no label.
  sel = lab.indexOf(-1);
  draw();
}
function setBusy(b) {
  busy = b; document.querySelectorAll('button').forEach((x) => { x.disabled = b; });
}
function runSolve() {
  if (busy) return;
  const t0 = performance.now(), r = solve(n, edges, 3000000), ms = Math.max(1, Math.round(performance.now() - t0));
  if (r.labels && isGraceful(n, edges, r.labels)) { lab = r.labels; sel = -1; msg = { t: i18nFmt("✓ Backtracking found a graceful labelling after exploring %nodes% search nodes (%ms% ms).", { nodes: r.nodes, ms }), cls: 'ok' }; }
  else msg = { t: i18nFmt("Gave up after %nodes% search nodes. This is a budget limit, not a counterexample: every tree this small is known to be graceful.", { nodes: r.nodes }), cls: 'bad' };
  draw();
}
// Stress test: hundreds of random trees, each solved and checked independently.
function stress() {
  if (busy) return;
  setBusy(true); addMode = false; leafBtn();
  const TOTAL = 300; let done = 0, ok = 0, tot = 0, worst = 0;
  function chunk() {
    let last = null;
    for (let i = 0; i < 12 && done < TOTAL; i++) {
      const N = 5 + Math.floor(Math.random() * 10), E = randomTree(N), r = solve(N, E, 200000);
      done++; tot += r.nodes; worst = Math.max(worst, r.nodes);
      if (isGraceful(N, E, r.labels)) ok++;
      last = [N, E, r.labels];
    }
    setTree(last[0], last[1], last[2] || null);
    if (done < TOTAL) {
      msg = { t: i18nFmt("Testing random trees… %done% / %total% done, %ok% labelled gracefully.", { done, total: TOTAL, ok }), cls: '' }; draw();
      setTimeout(chunk, 40);
    } else {
      setBusy(false);
      msg = ok === TOTAL
        ? { t: i18nFmt("✓ All %total% random trees (5–14 vertices) received a graceful labelling. Average %avg% search nodes, worst %worst%. No counterexample — as always.", { total: TOTAL, avg: Math.round(tot / TOTAL), worst }), cls: 'ok' }
        : { t: i18nFmt("%ok% of %total% trees labelled within the budget. The rest just ran out of search time — they are not counterexamples.", { ok, total: TOTAL }), cls: 'bad' };
      draw();
    }
  }
  chunk();
}
function leafBtn() {
  const b = $('leaf'); b.textContent = addMode ? "Add leaves: on" : "Add leaves: off";
  b.classList.toggle('on', addMode);
}

document.querySelectorAll('[data-preset]').forEach((b) => b.addEventListener('click', () => {
  if (busy) return; const [N, E] = PRESETS[b.dataset.preset](); setTree(N, E); msg = null; draw();
}));
$('leaf').addEventListener('click', () => {
  if (busy) return; addMode = !addMode; leafBtn(); sel = -1;
  msg = addMode ? { t: "Tap any vertex to hang a new leaf on it. Turn the mode off to label.", cls: '' } : null; draw();
});
$('solve').addEventListener('click', runSolve);
$('clear').addEventListener('click', () => { if (busy) return; lab = new Array(n).fill(-1); sel = -1; msg = null; draw(); });
$('stress').addEventListener('click', stress);
const [N0, E0] = PRESETS.cat(); setTree(N0, E0); draw();
Result
Console

By hand, even ten vertices can be surprisingly fiddly: fixing one red edge tends to break another. Press Solve and a backtracking search places the largest differences first and reports how many search nodes it explored — from a handful to a few thousand, in a few milliseconds. Then press Stress test: 300 uniformly random trees with 5 to 14 vertices, each solved and independently checked. Every one comes out graceful. That is exactly the situation mathematicians are in — overwhelming evidence, no proof.

What Is Actually Known

How hard is it, really? Not labelling one tree — proving that every tree can be labelled.

  • Brute force is hopeless in principle. A tree with nn vertices has n!n! possible labellings; for n=35n = 35 that is about 104010^{40}. Clever search is what makes small cases feasible — the demo's solver works through differences from the largest down (the difference n−1n-1 must join the labels 00 and n−1n-1), a constraint-propagation idea in the spirit of constraint satisfaction and depth-first search.
  • Verified by computer up to 35 vertices. Aldred and McKay (1998) checked every tree with at most 27 vertices; Michael Horton extended this to 29 (2003); and in 2010 Wenjie Fang reported, through a distributed verification project, that every tree with at most 35 vertices is graceful. The number of different trees grows exponentially with nn, so each extra vertex is costly.
  • Whole families are proved graceful. Paths, stars and caterpillars (trees that become a path once you delete their leaves) — already in Rosa's 1967 paper; trees with at most 4 leaves (Huang, Kotzig and Rosa, 1982); trees of diameter at most 5 (Hrnčiar and Haviar, 2001); and many more special classes catalogued in Gallian's Dynamic Survey of Graph Labeling. Still, even lobsters (one step beyond caterpillars) are only partly settled.
  • "Almost graceful" is now known for large trees. In 2016 Adamaszek, Allen, Grosu and Hladký showed that almost all trees are almost graceful. In a preprint from November 2025, Letzter, Pokrovskiy and Williams go further: for every ε>0\varepsilon > 0 and every large enough tree, there is a labelling with at least (1−ε)n(1-\varepsilon)n distinct edge differences. That is asymptotically close to graceful — but not graceful — and, as a recent preprint, it is still going through peer review.
  • The motivating problem was solved — without graceful labels. In 2020 Montgomery, Pokrovskiy and Sudakov, and independently Keevash and Staden, proved Ringel's conjecture for all sufficiently large nn: any tree with nn edges tiles the complete graph K2n+1K_{2n+1} with 2n+12n+1 copies. A graceful labelling would give such a tiling directly, but their proofs use probabilistic and absorption methods instead, so the graceful tree conjecture remains open. Preprints claiming a complete proof appear from time to time on arXiv; none has been accepted by the research community.

Why is it so stubborn? Graceful labellings do not build up locally: hanging one new leaf on a graceful tree can force you to relabel almost everything, so there is no obvious induction. The condition is global, rigid and arithmetic all at once. For general graphs it really can fail — cycles CnC_n are graceful only when n≡0n \equiv 0 or 3(mod4)3 \pmod 4 (Rosa, 1967), and the complete graph KnK_n only for n≤4n \le 4 (Golomb, 1972) — which is why "every tree" is such a strong and strange claim. Like the Collatz conjecture, it is a statement any schoolchild can test and no mathematician can settle.

Why It Matters

The conjecture was born from a real structural question, and its offspring reach well beyond puzzles:

  • Tiling complete graphs. Put the numbers 0,1,…,2n0, 1, \dots, 2n around a circle: that is the complete graph K2n+1K_{2n+1}. Draw a gracefully labelled tree with nn edges on it — its edges have the nn different "lengths" 1,…,n1, \dots, n. Rotate the drawing one step at a time, 2n+12n+1 times, and every edge of K2n+1K_{2n+1} is covered exactly once (Rosa's observation, 1967). That is why a graceful labelling would prove Ringel's conjecture for every nn, not just large ones.
  • Golomb rulers. A ruler with marks at 0,1,4,9,110, 1, 4, 9, 11 measures every distance between two marks at most once — a Golomb ruler. A graceful labelling of KnK_n would be a perfect ruler that measures every distance from 11 to the full length exactly once; Golomb's 1972 result says such rulers stop existing after 4 marks.
  • Engineering problems. In a 1977 survey, Gary Bloom and Solomon Golomb proposed numbered graphs for radio-frequency and radar pulse coding (avoiding repeated time or frequency gaps that cause interference), X-ray crystallography (where several structures can share the same set of distances), antenna placement in radio astronomy and communication-network addressing.
  • A testbed for search. Finding a graceful labelling is a crisp constraint satisfaction problem, related to graph colouring: good benchmarks for backtracking, local search and SAT-style solvers. Random trees for such experiments are generated with Prüfer codes — the same bijection behind Cayley's formula in spanning-tree counting.

Like Ramsey theory, graceful labelling asks how much order must hide inside every structure of a certain kind — and the honest answer, for now, is "we strongly suspect all of it."

Conclusion

The graceful tree conjecture is the kind of problem that makes combinatorics both delightful and maddening. The rule fits in one sentence. Checking a labelling takes a single pass over the edges. A laptop finds a graceful labelling for a random tree in a blink, and exhaustive searches have cleared every tree with up to 35 vertices. The neighbouring Ringel conjecture fell in 2020, and "almost graceful" is now within reach for large trees.

And still the exact statement — every tree is graceful — stands unproved, as it has since the 1960s. Kotzig reportedly called the flood of attempts a "disease". Try a few trees in the demo and you will see why it is contagious: every tree you build cooperates, and that only makes the missing proof more mysterious.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/graceful-tree-conjecture/Content licensed under CC BY-NC 4.0.