Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

From the Wikipedia article on graceful labeling:

... A major unproven conjecture in graph theory is the Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, which hypothesizes that all trees are graceful. The Ringel-Kotzig conjecture is also known as the "graceful labeling conjecture". ...

Is the conjecture still unsolved?

(for example I found Dhananjay P. Mehendale, "On Gracefully Labeling Trees", which claims that the conjecture is true).

share|cite|improve this question
See the latest version at you are refering to old version. – user73830 Apr 22 '13 at 17:06
I've already said this somewhere, but you should take any math paper not written in TeX with an additional dose of suspicion. – tomasz Jul 6 '13 at 14:29
up vote 4 down vote accepted

It's still open. At least if we are to believe this recent (2011) Stanford Thesis, which gives an extensive survey of the problem.

The problem is one of those 'disease' problems to which lots of people come up with bad proofs for. It does however appear to be solved for certain cases of trees.

share|cite|improve this answer

You can also find and trace news about best-known kinds of graph labeling, in a dynamic survey by J. A. Gallian. According to it's last version, the conjecture is still unproved.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.