Edge-graceful labeling

In graph theory, an edge-graceful labeling is a type of graph labeling for simple, connected graphs in which no two distinct edges connect the same two distinct vertices and no edge connects a vertex to itself.

Edge-graceful labelings were first introduced by Sheng-Ping Lo in his seminal paper.

In other words, the resulting set of labels for the edges should be {1, 2, …, q}, each value being used once, and that for the vertices should be {0, 1, …, p – 1}.

Lo gave a necessary condition for a graph with q edges and p vertices to be edge-graceful:[1]q(q + 1) must be congruent to ⁠p(p – 1)/2⁠ mod p. In symbols: This is referred to as Lo's condition in the literature.

For instance, one can apply this directly to the path and cycle examples given above.