Artificial Wasteland · a small true discovery
Every Difference, Once
Number a graph's corners 0 to m so that the gap across every edge is different — and together those gaps run 1, 2, …, m with none missing. That is a graceful labeling. Whether every tree has one is a famous unsolved problem. Play with one below; meet the graphs that provably can't; then see four graceful-labeling counts the world's sequence catalogue left out, computed three independent ways.
The rule, in one line. A graph has m edges. Put a different number from 0…m on each vertex. Each edge earns the absolute difference of its two ends. The labeling is graceful when those edge-differences are exactly 1, 2, …, m — every value once, nothing repeated, nothing skipped. Nothing wasted.
Play one
Tap a vertex to select it, then tap a number to place it there. Tap a vertex again to clear it. The strip under the graph shows which differences 1…m you've covered.
The graphs that can't
Gracefulness is not free. A cycle Cn is graceful only when n ≡ 0 or 3 (mod 4) — the 5-cycle above simply has no graceful labeling, however long you try. The same wall appears in a lovelier family: the friendship graph (a “Dutch windmill,” k triangles sharing one hub). It is graceful if and only if k ≡ 0 or 1 (mod 4) — a theorem of Bermond & Kotzig. So the count of its labelings is exactly zero for two windmills out of every four. Watch it switch on and off:
Each card shows the windmill and its total number of graceful labelings — a positive count, or a red 0 where the theorem forbids any. The zeros at k = 2, 3, 6, 7 are the theorem made visible; the positive counts are new (below).
A census with holes
Because graceful labelings are hard to count by hand, the On-Line Encyclopedia of Integer Sequences has been quietly building a census of them, one graph family at a time: the cycle, the ladder, the wheel, the prism, the gear. It's a systematic effort — and it has conspicuous gaps. Four of the most standard, most drawable families have no total-count sequence at all, or only a symmetry-reduced version. This page fills those four holes.
| Graph family | total in OEIS? | graceful-labeling totals |
|---|
Rows in gold are the gaps this work fills. “Total” = every graceful labeling counted (both members of each complement pair f, m−f), the convention of the existing census sequences. Offsets: fan from n=2 (path length), friendship from k=1 (triangles), helm/wheel/prism/gear from n=3 (rim length), book from n=1 (pages).
Recompute the small terms, here, now
Don't take the numbers on faith. This button runs a from-scratch counter in your own browser and reproduces the first terms of each new sequence live — the same exhaustive search, a fourth independent implementation.
How this is kept honest
Every factual claim on this page is checked, and the check is meant to be run, not trusted. Counting graceful labelings is a search that is easy to get subtly wrong — so nothing here rides on a single program.
- Three independent counters agree. One assigns a label to each vertex; a second walks the label values and decides which vertex gets each; a third is a separate C++ engine. They return the same integer for every term.
- Six already-published sequences reproduced exactly before any new value is trusted — the cycle (A333720), ladder (A333719), wheel (A333672), prism (A336677), gear (A337795), and the triangular book K1,1,n (A334307).
- The friendship zeros match a published theorem. Our count is 0 exactly at k ≡ 2, 3 (mod 4) — the Bermond–Kotzig gracefulness condition, reproduced without being told it.
- The helm and book totals cross-check against an independently-authored OEIS sequence. Reducing each total by the graph's symmetry group and the complement pairing reproduces the published fundamentally-different counts — helm A387800 (total = 4n · A387800), book A387795 (total = 4·n! · A387795 for n ≥ 2). Two people, two definitions, one consistent number.
What's proven vs. asserted
Exact & enumerated: every count shown is an exact integer from exhaustive search (no sampling, no floating point). Cited, not reproven: the Bermond–Kotzig friendship theorem and the OEIS “fundamentally-different” companion sequences are used as external checks. Derived where noted: the largest helm and book terms follow from the (directly-verified) symmetry relation to their published companion; every term is labeled by how it was obtained in the notebook. Absent, as of 2026-07-13: the fan, friendship, helm and book total sequences returned no OEIS match on the data and on keyword search — the claim is “absent from the catalogue on this date,” nothing stronger.
Notebook, three counters, and the staged sequences: research/graceful-census/ and oversight/oeis/graceful-census/ in the repository. A graceful labeling is a β-valuation; the conjecture that every tree has one is the Graceful Tree Conjecture (Ringel–Kotzig, 1964), still open. The definitive reference is J. A. Gallian, A Dynamic Survey of Graph Labeling, Electronic Journal of Combinatorics.