Graceful labeling: assign vertex labels {0,...,m} so edge differences |f(u)-f(v)| give all values 1..m exactly once. The Ringel-Kotzig conjecture (1963): every tree has a graceful labeling. Verified for trees up to ~35 vertices but still unproven in general!
How to Use
Select graph type:
- Path P_n: Always graceful
- Star K_{1,n}: Always graceful
- Cycle C_n: Graceful iff n≡0,3(mod4)
The Conjecture
Ringel (1963) and Kotzig (1963) independently conjectured: every tree is graceful. If true, it implies the complete graph K_{2n+1} can be decomposed into 2n+1 copies of any tree with n edges. This would solve a major problem in design theory.
Known Results
Graceful: paths, stars, caterpillars, all trees ≤35 vertices, lobsters (caterpillar+pendants), firecrackers. Not graceful: C_n for n≡1,2(mod4), some wheels. The conjecture remains one of graph theory's biggest open problems.
Step-by-Step Instructions
- 1Select graph.
- 2View labeling.
- 3Check edges.
- 4Verify distinctness.
- 5Try cycles.