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).

  • $\begingroup$ See the latest version at arxiv.org/ftp/math/papers/0503/0503484.pdf you are refering to old version. $\endgroup$ – user73830 Apr 22 '13 at 17:06
  • $\begingroup$ I've already said this somewhere, but you should take any math paper not written in TeX with an additional dose of suspicion. $\endgroup$ – tomasz Jul 6 '13 at 14:29
  • $\begingroup$ the definition of graceful labeling is wrong in the referred paper $\endgroup$ – vidyarthi Apr 16 at 14:32

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.


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.


Another paper just came out on it here: https://arxiv.org/abs/1811.07614 I can't read it well enough to say whether it's solved or not though.

  • $\begingroup$ even I think its solved $\endgroup$ – vidyarthi Apr 16 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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