Edge-graceful Labeling - A Necessary Condition

A Necessary Condition

Lo gave a necessary condition for a graph to be edge-graceful. It is that a graph with q edges and p vertices is edge graceful only if

is congruent to modulo p.

or, in symbols,

This is referred to as Lo's condition in the literature. This follows from the fact that the sum of the labels of the vertices is twice the sum of the edges, modulo p. This is useful for disproving a graph is edge-graceful. For instance, one can apply this directly to the path and cycle examples given above.