## Golombs Graceful Graphs

One of the least explored areas of modern mathematics is a class of problems that combine graph theory and arithmetic. Recreational problems of this type have been discussed before in my earlier book collections; for example, in the chapter on Magic Stars and Polyhedrons in Mathematical Carnival. In this chapter we take up a family of numbered-graph problems that has recently been defined and developed by Solomon W. Go-lomb, professor of engineering and mathematics at the University of Southern California. He is the author of Polyominoes (Scribner's, 1965), numerous articles on recreational topics and many technical papers. What follows is extracted from his correspondence and from his paper "How to Number a Graph."

Golomb has coined the term "graceful graph" for any graph that can be "gracefully numbered." He explains this terminology with a simple example: The graceful numbering of the graph shown in Figure 90. It is called the "complete graph for four points" because every pair of its four nodes is joined by a line called an edge. The graph is topologically equivalent to the

Figure 90

Figure 90

A graceful graph

skeleton of a tetrahedron. It is planar because it can be drawn on the plane without intersecting edges. A graph, as we shall see, need not be planar in order to be gracefully numbered, but it must be without loops (lines joining a node to itself) or multiple edges (more than one edge connecting the same pair of nodes).

Each node is labeled with a nonnegative integer. The lowest integer (by convention) is 0, and no two integers may be alike. After the nodes are numbered every edge is labeled with the difference between the numbers of its two end nodes. Like node numbers, all edge numbers also must be distinct (no two alike). The objective is to do all these things and keep the largest node number as small as possible. Obviously it cannot be smaller than the number of edges. If the largest node number equals the number of edges, e, the edge numbers will run consecutively from 0 through e, and we shall have achieved a graceful numbering. The number e will represent three values: the total number of edges, the highest node number and the highest edge number. Any graph that can be gracefully numbered is a graceful graph. Some graceful graphs have only one basic numbering, others more than one. (Trivial variations obtained by such symmetry operations as rotations and reflections, or by replacing each node number n by e—n, are not considered different.) A graph that cannot be numbered gracefully is called an ungraceful graph.

As Golomb points out, every complete graph can be drawn with all its nodes on a straight line and the remaining edges can be added as curved lines [see left side of Figure 91]. Let us go further. Imagine that the straight line is the edge of a ruler with a length equal to the largest edge number of a numbered graph. The nodes of the graph are marks on the ruler at points that correspond to their numbers, each number indicating the mark's distance from the zero end of the ruler. Golomb calls such a ruler a "Euclidean model" of a numbered complete

Figure 91

Figure 91

Ruler version (left) of a complete graph (right)

chapter 15

graph. The problem of gracefully labeling a complete graph of n nodes is equivalent to the problem of putting n marks on a ruler (always including the ruler's two ends as marks) so that every distance between a pair of marks is a distinct integer. In this example the ruler is marked at points 0, 1, 4 and 6, the node numbers of the complete graph for four points after it is gracefully numbered. Such a ruler clearly can measure lengths of one, two, three, four, five and six units. At the right of the ruler is shown another way of drawing the complete graph for four points: as a four-sided polygon with all its diagonals. (The intersection of the diagonals is not, of course, a node). Note that the distances between adjacent marks on the ruler, together with the ruler's length, correspond to the perimeter numbers of the gracefully labeled square graph.

A closely related but less restricted ruler problem was discussed in Chapter 6 of my book The Incredible Dr. Matrix. Dr. Matrix' rulers measure all integral distances from zero to the length of the ruler, but the numbers of its "edges" (distances between any pair of marks) are not required to be different. With the added proviso that all such distances must be different, Dr. Matrix' ruler problem becomes identical with the problem considered here: That of finding a ruler with marks that correspond to the graceful numbering of a complete graph with n nodes. Golomb proves in his paper that this can be done only if n is 1,2, 3, or 4. Expressed differently, no complete graph for n points, when n exceeds 4, can be gracefully numbered.

If we keep the requirement that all distances between pairs of marks must be different, but we do not insist that they run consecutively from zero to the ruler's total length, we can still look for the shortest possible ruler of n marks (end points are included as marks) on which all distances between a pair of marks (which correspond to the edge numbers of the complete graph for n points) are different. In the chart of the shortest-known rulers when n is from 2 through 11 [see Figure 92], only the first three entries are solutions to Dr. Matrix' ruler problem. They correspond to the graceful numbering of complete graphs for two, three and four points. The other rulers do not have consecutive integral distances from zero to the ruler's length; they correspond to what Golomb calls the "best" numbering of complete graphs for more than four points. The numbers in each row give the distances between adjacent marks on rulers of two, three, four, . . . , 11 marks. The chart, which extends downward to infinity, is called the Golomb triangle.

 NODES EDGES DISTANCES BETWEEN ADJACENT MARKS LENGTH 2 1 1 1 3 3 1 2 3 4 6 1 3 2 6 5 10 1 3 5 2 11 6 15 1 3 6 5 2 17 7 21 1 3 6 8 5 2 25 8 28 1 3 6 11 8 5 2 36 9 36 1 3 12 10 8 6 5 2 47 10 45 1 3 6 12 16 11 8 5 2 64 11 55 1 8 10 5 7 21 4 2 11 3 72

GOLOMB'S TRIANGLE: Shortest Golomb rulers known in 1972.

GOLOMB'S TRIANGLE: Shortest Golomb rulers known in 1972.

We can put the difference between Dr. Matrix' rulers and Golomb's rulers as follows. Dr. Matrix' rulers minimize the number of marks for a ruler of length k that can measure all integral distances from 1 through k. Golomb's rulers do not necessarily include all the integral distances from 1 through k; with Golomb's rulers, for a ruler with a given number of marks, the length of the ruler is minimized and all the integral distances the ruler does measure are different. If we draw a graph corresponding to a Dr. Matrix ruler, we may find two edges with the same edge number. By omitting all edges with duplicate numbers we can get a graceful graph that Golomb calls a "graceful approximation" of a complete graph. For example, by dropping one edge (the line between points 1 and 4) from a complete graph for five points [see Figure 93] the graph can be gracefully numbered. It is equivalent to Dr. Matrix' ruler with marks at points 0, 1, 4, 7 and 9.

It is worth noting that on Golomb rulers not only are all differences between pairs of node numbers distinct, but also all

Graceful graph for a Dr. Matrix ruler

sums of pairs of node numbers, including the pairing of a node number with itself. "That this is equivalent to the differences being distinct is surprising," Golomb writes, "but fantastically simple to prove." (Proof: if a — b = c — d, then a + d = b + c, and conversely.)

With a yardstick, or 36-unit ruler as an example, here is a quick way to prove that all distances measured by a Golomb ruler are distinct. The yardstick has eight marks. The top row [see Figure 94], taken from Golomb's triangle, gives the distances between adjacent marks on this ruler. These seven numbers, together with the ruler's total length, correspond to the eight edge numbers on the perimeter of an eight-sided polygon when it is made into a complete graph by drawing all its diagonals and then numbered as gracefully as possible. The

Figure 94 1 3 6 11 8 5 2 4 9 17 19 13 7 10 20 25 24 15 21 28 30 26 20 33 32 34 35 36

Proof for eight-mark Golomb ruler second row of numbers is obtained by adding successive pairs of numbers in the row above it. The third row consists of adding successive triplets in the top row, the fourth row of adding successive quadruplets, and so on. The bottom number is the ruler's length. It is, of course, the sum of all the numbers in the top row. The 28 numbers of this triangle are the 28 edge numbers of the complete graph for eight points when it is given the best ungraceful numbering. If all these numbers are different, no two edge numbers of the complete graph will be alike and no two distances between pairs of marks on the corresponding ruler will be alike.

Golomb admits that for all rulers longer than six units the results were obtained (by himself and others) partly by trial and error. They have not yet been proved to be rulers of minimal length. (The ruler of length 47, for nine marks, was first found in 1965 by Matthew J. C. Hodgart of Brighton in England; the ruler of 72 lengths, for 11 marks, by Robert Reid of Miraflores in Argentina, also in 1965.) Perhaps readers can improve on these results or extend the triangle farther downward.

One of the many unusual properties for all graceful graphs discovered by Golomb is that the nodes of such graphs can always be divided into two sets—those with even numbers and those with odd—and the number of edges connecting the two sets will be [ (e + l)/2], where e is the total number of edges in the graph. The brackets mean that the expression is rounded down to the nearest integer. Golomb calls this a "binary labeling." For example, the even set of nodes in the graph at the left of Figure 91 are numbered 0, 4 and 6, and the odd set has only the number 1. Inspection shows that the two sets are indeed joined by [(6+ l)/2] = 3 edges.

Moreover, as Golomb proves, if all the nodes of a graph are of even order (attached to an even number of edges), the graph is graceful only if [(e+ l)/2] is even. When this value is odd, binary labeling is impossible and therefore the graph cannot be gracefully numbered. Of the topologically distinct graphs with five or fewer nodes, only three are ungraceful. All three have five nodes and all their nodes are of even order. The three graphs violate Golomb's condition that [(^ + l)/2] must be even [see Figure 95]. Note that the first two graphs are planar whereas the third, the complete graph for five points, is not. This shows that not all planar graphs, and not all non-planar graphs, are graceful. Can a nonplanar graph be graceful? Yes, as the graceful labeling of the Thomsen graph shows [see Figure 96], The Thomsen graph is sometimes called the utilities graph because it diagrams the well-known (and unsolv-

Figure 96

Figure 96

8/

\ 2 /

5

• \ /

9

e\

A graceful numbering of the Thomsen graph

A graceful numbering of the Thomsen graph able) puzzle in which three houses are each to be connected to three utilities without any crossing of edges. The Thomsen graph is one of an infinite family of graphs, known as "complete bipartite graphs," in which every node in a set of a nodes is joined to every node in a set of b nodes, but nodes within each set are not connected. Golomb has established that all complete bipartite graphs are graceful.

Skeletons of polyhedrons can be represented as planar graphs known as Schlegel diagrams. Of the five Platonic solids only the dodecahedron and icosahedron have not been shown to be graceful. We have seen how to gracefully number the tetrahedron. Can the reader gracefully number the Schlegel diagrams of the cube and octahedron [see Figure 97] before Go-lomb's labelings are given in the Answer Section? Can he do the same for the diagram of the skeleton of the Great Pyramid of Egypt? Can he discover graceful numberings for the dodecahedron or the icosahedron?

Three other graceful graphs by Golomb have six, seven and

octahedron (center) and Great Pyramid (right)

Figure 98

Figure 98

and ten nodes

10 nodes [see Figure 98], Can the reader number these also before the solutions are given?

In addition to complete bipartite graphs there are other infinite families of graceful graphs. One found by Golomb is shown in Figure 99. The question arises: As the number of nodes approaches infinity, does the fraction of graceful graphs among all graphs of n nodes approach a limit? If so, what is the limit? For several years no fractional value from 0 through

Figure 99

Figure 99

An infinite family of graceful graphs

1 was excluded, but recently Paul Erdôs has been able to show that the limit is 0. His proof, not yet published, is difficult. Gary Bloom and Herbert Taylor found a fairly easy way to show that the number of graceful graphs with e edges is equal to or less then e, from which it follows at once that the limit is 0.

Although many unsolved problems about graceful graphs, some very technical, have now been cleared up by Golomb, Erdôs, and others, there are still several major questions that remain unanswered:

(1) What are the necessary and sufficient conditions for a graph to be graceful? It is not even known if all tree graphs are graceful. (Tree graphs are discussed in Chapter 17 of my Mathematical Magic Show.) Gerhard Ringel in 1963 apparently was the first to conjecture, Ln a different terminology and independently of Golomb's work, that all tree graphs can be gracefully numbered. This has been the subject of several papers by Alexander Rosa and other Czechoslovakian mathematicians. The conjecture has been established only for special kinds of trees such as "caterpillars"; trees with every node on a central stalk or only one edge from the stalk [see Figure 100], In a typical gracefully numbered caterpillar the edge numbers run consecutively from one end of the tree to the other.

Figure 100

Figure 100

A graceful caterpillar

Golomb has discovered a similar algorithm for gracefully numbering an infinite class of polyomino graphs such as the pentomino and the heptomino [see Figure 101]. Note how the consecutive numbers run diagonally upward, from left to right. Unfortunately there is an infinite class of polyominoes with a greater degree of concavity (the degree is not easy to define)

 3 8 2 11 7 4 12 6 H 14 13 1 Graceful polyominoes for which this procedure fails even when they can be gracefully numbered. A simple graph found by Golomb [see Figure 102] is particularly ungraceful because it is not ruled out by any known general theorem. Figure 102 Figure 102 (2) What are the rules for forming Golomb's triangle? Put another way, is there a general algorithm for finding the shortest rulers that correspond to the best ungraceful numbering of a complete graph for more than four points? (3) Is there a graph that, when numbered as gracefully as possible, violates the conjecture that on all such graphs the highest node number and the highest edge number are equal? Golomb is now searching for a counterexample; a graph with the best numbering but with a highest node number that exceeds the highest edge number. (It cannot be the other way around.) "If I find one," Golomb writes in a letter, "the graph will not only be ungraceful but downright disgraceful." Solutions to the graceful-graph problems
0 0