Graceful Graphs: Basic Definitions

As you read through these pages, I encourage you to experiment with the ideas presented. Familiarity working with graceful labellings is essential to understanding them.

From the basic definition of graceful graphs, many facts become immediately available. The first is that there are exactly N! graceful labellings on N edges.

One way to realize this is to consider the different ways to make each edge label. The edge labelled N can be made in only one way: with the vertices 0 and N. The edge labelled N-1 can be made in two ways, using either (0, N-1) or (1, N). Either pair has absolute difference N-1. Continuing in this way, you eventually reach the edge labelled 1, which can be made in N different ways. Because each choice is independent of the others, it follows that there are 1*2*3*...*N = N! graceful labellings on N edges.

Figure 2-1: There are N! graceful labellings on N edges.

However, this count does not tell the true story. Many of these labellings result in equivalent (isomorphic) graphs. In fact, given a graceful labelling of the vertices, you can construct another graceful labelling by subtracting each vertex label from N. This doesn't change the edge labellings, because each edge (u, v) is now (E-u, E-v) and the absolute difference is the same: | (E - u) - (E - v) | = | u - v | So the new graph has the same edge labels but different vertex labels. Some authors call this the vertex complementary labelling.

Figure 2-2: Two (equivalent) graceful labellings of K4.

So the real question becomes: Which kinds of graphs are graceful? Are all trees graceful? What about all graphs that contain a single cycle? Although simple to pose, both of these questions (and many others) remain unanswered today.

Although it's not yet known what makes a graph graceful, there are several known reasons a graph may fail to be graceful:

• Too many edges (e.g., the complete graph on 5 vertices, K5, is not graceful)
• Too few edges (e.g., the union of the path P2 with itself is not graceful)
• Parity (e.g., the cycles C6 and C7 are not graceful)

Figure 2-3: K5, P2 union P2, and C6 are not graceful

This last condition can be stated formally as:

Theorem (Rosa): If a graph G with E edges is Eulerian, then G is graceful only if |E| = 0, 3 (mod 4).

Corollary: Cycles Cn are graceful if and only if n = 0, 3 (mod 4).

Some graceful graphs are disconnected.