Let T be a tree on n vertices and let f : V → {1, 2,..., n} be a valuation on V(T). Then f is called a graceful labeling of T if ∣f(v) -- f( u)∣ is unique for each edge vu ∈ E(T). We will establish the connection between gracefully labeled trees and the Ringel-Kotzig Conjecture, as well as survey several classes of trees that have been proven graceful as a result of efforts to show that all trees are graceful. |