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.[1]
Given a graph, we denote the set of its edges by and that of its vertices by . Let be the cardinality of and be that of . Once a labeling of the edges is given, a vertex of the graph is labeled by the sum of the labels of the edges incident to it, modulo . Or, in symbols, the induced labeling on a vertex is given by
V(u)=\SigmaE(e)\mod|V(G)|
The problem is to find a labeling for the edges such that all the labels from to are used once and that the induced labels on the vertices run from to . In other words, the resulting set of labels for the edges should be