A 
-graph
is edge-graceful if the edges can be labeled 1 through
in such a way that the labels induced on the vertices by summing over incident edges
modulo 
are distinct. Lo (1985) showed that a graph 
is edge-graceful only if 
. Since then, many families of graphs have been
shown to be edge-graceful. These are exhaustively enumerated in Gallian's dynamic
survey, which also contains a complete bibliography of the subject.
In 1964, Ringel and Kotzig conjectured that every tree of odd order is edge-graceful. No known connected graph which satisfies Lo's condition has failed to be edge-graceful.
The simplest known graph which satisfies the condition and yet fails to be edge-graceful
is the disjoint union of 
with 
(Lee et al. 1992). A later proof by Riskin and Wilson
(1998) constructs infinite families of disjoint unions of cycles which satisfy Lo's
condition and yet fail to be edge-graceful.
