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