A graph is a collection of nodes (called vertices), some of which are joined together by edges. Connected simple graphs are graphs with a path between any two vertices, has no vertex which has an edge joined to itself, and does not have more than 1 edge from a vertex to another vertex. A connected graph is a tree if it has no cycles, meaning that if we start at any vertex and follow some path along the graph then we won’t be able to return back to the initial vertex without traversed some edge more than once. On a graph we define a labelling to be a mapping from the vertex set to the real numbers. That is, we assign each vertex a number. There exist many different types of labellings on a graph that are classified by some condition to which the labelling must follow. One of these labellings is called graceful labelling and is defined as follows. Let n be the number of vertices and m be the number of edges in a graph G. If we can label the vertices with the nonnegative integers from 0 to m such that the positive difference of the labels of two connected vertices is unique for all pairs of connected vertices, then we say that the graph is graceful and furthermore say that the labelling is a graceful labelling. One problem that arises when attempting to gracefully label a connected simple graph is finding which n numbers from 0 to m to choose. This problem is reduced significantly for connected trees. Since trees have n-1 edges we would need to label the vertices with the numbers from 0 to n-1 and since there are only n such numbers we can choose from, it is clear that we need to use all the integers from 0 to n-1. Using this fact, it becomes easier to find the graceful labelling as it is now simply a problem of finding which numbers go to which vertices. When trying to find the graceful labels of some tree, it seems as though there always exists a labelling and intuition makes us want to believe that all trees are graceful, however we cannot consider it true until we prove it and this very question of whether trees are graceful is a major conjecture in graph theory called the graceful tree conjecture.
Aditya Joshi
The University of Newcastle
