Graceful Tree Conjecture

Importance: High ✭✭✭
Subject: Graph Theory
» Coloring
» » Labeling
Recomm. for undergrads: no
Posted by: kintali
on: July 13th, 2007
Conjecture   All trees are graceful

Label the vertices of a simple undirected graph $ G(V,E) $ (where $ |V| = n $ and $ |E| = m $) with integers from $ 0 $ to $ m $. Now label each edge with absolute difference of the labels of its incident vertices. The labeling is said to be graceful if the edges are labelled $ 1 $ through $ m $ inclusive (with no number repeated).

A graph is called graceful if it has at least one such labeling. This labeling was originally introduced in 1967 by Rosa. The name graceful labeling was coined later by Golomb.

Gracefully labeled graphs serve as models in a wide range of applications including coding theory and communication network addressing.

The graceful labeling problem is to determine which graphs are graceful. It is conjectured (by Kotzig, Ringel and Rosa) that all trees are graceful.

Despite numerous (more than 200) publications on graceful labeling for over three decades, only a very restricted classes of trees (and also of some other graphs) have been shown to be graceful. These restricted classes include paths, stars, complete bipartite graphs, prism graphs, wheel graphs, caterpillar graphs, olive trees, and symmetrical trees.


* indicates original appearance(s) of problem.


Many, many references on the topic appear in Joseph Gallian's "A Dynamic Survey of Graph Labeling", section 2 ( ).

Graceful Tree examples

If you want to develop intuition for a proof, feel free to use this program I wrote ( Good luck.

applications of graceful graphs

can you explain some applications of graceful graphs

Apllication of graceful labeling

I want the application of graceful label

graph theory

Can you pls send some applications of gracefulgraphs

Tentative proof

I just saw this paper on arxiv, entitled "A complete proof of The Graceful Tree Conjecture using the concept of Edge Degree".

I'm surprised to see such a short proof for such a long-standing open problem, but surely people who are a lot more into the subject than I will be able to provide more constructive comments on the paper.

Re: Tentative proof

It's a bit worrisome that this is already the eight version on the arXiv ... this probably means that the previous seven versions had some sort of flaw in it ... I haven't read the paper though ...

injective labeling

Rosa (1967) required the labeling to be injective.


The complete bipartite graph isn't a tree.

not a problem

graceful labellings are defined for arbitrary graphs, not just trees.

no duh..

I was just pointing out the statement

"...only a very restricted classes of *trees* have been shown to be graceful. *These* restricted classes include...the complete bipartite graph".

doesn't make sense.

Re: wording

Truly, this was unfortunate choice of wording; I corrected it. (Btw to provide a graceful labeling for complete bipartite graphs is quite an easy exercise.)

graceful labeling of complete bipartite graphs

how to give a graceful labeling to complete bipartite graph. Can u suggest some efficient algorithm or scheme for that Plz email it to if u have any...


Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.