Is the graceful labeling conjecture still unsolved? 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).

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.