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. Definition Given a graph , we denote the set of edges by and the 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 the vertex is given by where is the label for the vertex and is the assigned value of an edge incident to . The problem is to find a labeling for the edges such that all the labels from 1 to are used once and the induced labels on the vertices run from 0 to . In other words, the resulting set for labels of the edges should be and for the vertices. A graph is said to be edge-graceful if it admits an edge-graceful labeling. Examples Cycles Consider the cycle with three vertices, . This is simply a triangle. One can label the edges 1, 2, and 3, and check directly that, along with the induced labeling on the vertices, this gives an edge-graceful labeling. Similar to paths, is edge-graceful when is odd and not when is even. Paths Consider a path with two vertices, . Here the only possibility is to label the only edge in the graph 1. The induced labeling on the two vertices are both 1. So is not edge-graceful. Appending an edge and a vertex to gives , the path with three vertices. Denote the vertices by , , and . Label the two edges in the following way: the edge is labeled 1 and labeled 2. The induced labelings on , , and are then 1, 0, and 2 respectively. This is an edge-graceful labeling and so is edge-graceful. Similarly, one can check that is not edge-graceful. In general, is edge-graceful when is odd and not edge-graceful when it is even. This follows from a necessary condition for edge-gracefulness. A necessary condition Lo gave a necessary condition for a graph with edges and vertices to be edge-graceful: must be congruent to .