6.3. Graceful graphs

A graph G of size m is called graceful if it is possible to label the vertices of G with distinct elements from the set  in such a way  that  the induced  edge  labeling,  which prescribes the integer  to the edge joining vertices labeled i and j, assigns the labels  to the edges of G.

Such labeling called graceful labeling.

Not every graph is graceful. See  or .

The gracefulness  of a graph G with  and without isolated vertices is the smallest positive integer k for which it is possible to label the vertices of G with distinct elements from the set  in such a way that distinct edges receive distinct labels.

Such vertex labelings always exist: if we order to  the label .

  • For every graph G of order n and size m without isolated vertices .
  • All connected graphs of order at most 4 are graceful.
  • There are exactly three connected nongraceful graphs of order 5. In each case the gracefulness is one more than the size.

We return to the decompositions and give a constructive proof for the next theorem:

Theorem 8.34.: For every graph H without isolated vertices, there exists a regular

H-decomposable graph.

Proof.

Let  be a graph without isolated vertices and suppose that .

Hence there exists a labeling  of vertices of H so that distinct edges are labeled differently and

.

We now construct a regular H-decomposable graph G of order .

Let  and arrange these vertices cyclically in clockwise order about a regular p-gon.

Next we define a graph  by

and

.

For , define  by cyclically rotating  through a clockwise angle of  radians. Therefore, ,

and

.

The process is completed by defining

The graph G is therefore decomposable into the graphs , each of which is isomorphic to H, and G is 2m-regular.

 

Theorem 6.7. If G is a graceful graph of size m, then there exists a partition of  into two subsets  and   such that the number of edges joining  and  is .

Proof

Let a graceful labeling of G given. Denote the set of vertices labeled with an even integer by  and the set of vertices labeled with an odd integer by .

All edges labeled with an odd integer must join a vertex of  and a vertex of .

Since there are  edges, the result follows.

Theorem 6.8. If G is a graceful eulerian graph of size m, then

.

Proof.

Let  be an eulerian circuit of G, and let a gra-ceful labeling of G be given that assigns the integer  to  for , where  if . So, the label of the edge  is . Observe that

for . Thus the sum of the label of the edges of G is

that is the sum of the edge labels of G is even. However, the sum of the edge labels is 

so  is even.

Consequently,  or , which implies the statement.

Theorem 6.9. The cycle  is graceful iff

.

We saw before that the complete graphs  and  are graceful. It is easy to see that  is also graceful. The next result of Golomb shows that there are no other graceful complete graphs.

Theorem 6.10. (Golomb, 1972): The complete graph  is graceful iff .