DMontae Jones

MTH 390 – Combinatorics

Dr. Robert Molina

8 December 2011

The Reconstruction Conjecture – A Brief Introduction to Graph Reconstruction, Graph Properties, and Kelly’s Lemma

Abstract

The Graph Reconstruction Conjecture formally proposes that all finite, simple, undirected graphs with at least three vertices, or more, can be determined by the collection set of their vertex-deleted subgraphs. The content of this paper will focus its attention toward finite, simple, undirected graphs and provide a brief introduction of the conjecture and properties of graphs that have been uncovered through the conjecture. Furthermore, this paper will review an approach to the conjecture due to Kelly (1957), and other theorems and corollaries that branched from Kelly’s original lemma.

Introduction

Paul J. Kelly, in 1957, wrote his doctoral dissertation under the supervision of Polish-American Mathematician Stanislaw M. Ulam. Kelly’s dissertation proved the Reconstruction Conjecture held true for trees. Ulam officially published a statement of the conjecture, which was known to him since 1929, in 1960. It is said that Ulam published the conjecture as a result of collecting various mathematical problems proposed by some of his graduate students. As a result of this, his credit for the proposal of the unsolved problem was questioned. This led to some confusion as to whose name would be associated with the conjecture. None the less, the conjecture has been commonly accepted by the name the Kelly-Ulam conjecture. For the purpose of this paper, it will be generally referred to as the Reconstruction Conjecture. The Reconstruction Conjecture asserts that any finite, simple, undirected graph with at least three vertices can be uniquely determined by its collection of vertex-deleted subgraphs. The conjecture has been vastly reviewed as one of the most challenging and compelling unsolved problems in Graph Theory, which has resulted in numerous surveys regarding its analysis and solution. One of the first approaches to the conjecture was made by Kelly (1957) as previously stated. His proof that the conjecture held true when restricted to trees (stating that trees are reconstructible) has led to further work on the reconstruction of other classes of graphs. Over the years, there has been substantial progress made and knowledge of the implications of the conjecture has grown vastly. It is now known that certain classes of graphs do exist where the conjecture holds true, such as regular graphs. There also classes of graphs that exist in which the conjecture is false, such as tournaments. Unfortunately, the general case for all graphs has yet to be solved. Another accomplishment made through the conjecture is the various properties of a graph that can be determined from its vertex-deleted subgraphs. In this paper, a brief introduction to the Reconstruction Conjecture will be given. Furthermore, a few properties of graphs will be analyzed from their collection of vertex-deleted subgraphs. Finally, an introduction of the lemma and other corollaries proposed by P.J. Kelly will be overviewed.
Notation and Definitions

A graph [pic] is defined by having an ordered pair [pic] such that [pic]is the set of vertices and [pic] is the set of edges in graph[pic]. Given a graph[pic], and a vertex of[pic],[pic] the degree of the vertex, where [pic] will be denoted by[pic], which is the number of edges incident to[pic]. An undirected graph is a graph in which the edges have no orientation or direction. A directed graph, or digraph, is a graph in which the edges are direct from one vertex to another vertex in a graph[pic]. Much of this paper will involve analyzing the vertex-deleted subgraphs of a graph. These are graphs in which one vertex and all of the edges incident to that vertex have been deleted from the original graph. A vertex-deleted subgraph will be referred to by the notation [pic] which is equivalent to[pic]. A card of [pic] will be defined as an unlabeled graph formed by deleting one vertex and its incident edges from the original graph. The deck,[pic], of a graph is the family of unlabeled, vertex-deleted subgraphs of the original graph [pic]. A regular graph is a graph in which all of its vertices have the same degree. A complete graph will be denoted by[pic], where [pic] is the number of vertices in that graph. A graph is considered reconstructible if and only if you can uniquely determine the original graph, up to isomorphism (structurally identical), from the vertex-deleted subgraphs.
Properties of Graphs

The following theorem asserts that from the collection of vertex-deleted subgraphs of a graph[pic], some information about the original graph can be derived.

Theorem 1. The number of vertices and the number of edges of a graph G can be calculated from its vertex-deleted subgraph list.

Proof. The size of the collection of vertex-deleted subgraphs is n. From this, it is clear that from the collection size of vertex-deleted subgraphs it can be deduced that[pic], which is also equal to the number of cards in [pic] Furthermore, since each edge in [pic]only appears in the [pic] subgraphs that do not contain either of its endpoints, it provides that the sum [pic] counts each edge [pic] times, where [pic]is the number of edges of each subgraph of[pic]. Thus, the number of edges in G can be expressed as
[pic]

Furthermore, through the properties of [pic]and its subgraphs, the degree of each vertex can be determined. The Lemma asserts that for all vertices that are an element of the vertex set of the graph, the[pic]. Since the edges of the original graph [pic] can be determined from the deck the degree of each vertex in the vertex set of [pic] can be determined. Therefore, the entire degree sequence of a graph [pic]can be determined through this property. For example, let the vertex-deleted subgraphs of a graph G be defined by the graphs in figure 1.

Figure 1: A collection of vertex-deleted subgraphs of[pic].

From the unlabeled deck of a graph [pic], the values that are known include the vertex set of the original graph,[pic] and the edge set of the original graph,

[pic]

From these quantities, and using the properties of the degree of each vertex, it can be asserted that the degrees of missing vertices in order are [pic] and [pic]. Noting the degree of the missing vertex in subgraph two to be 4, it can be asserted that the vertex is connected to each of the other vertices. Thus, the graph G must be represented by figure 2.

[pic]

Figure 2: The original graph[pic], uniquely determined

Graph’s also have recognizable properties. Let the graph G have some property. If whenever there is a graph H with the same deck as G, then it must have the same property. This property is then called recognizable. Since the degree sequence of a graph can be uniquely determined given the deck of that graph, then regular graphs (a graph in which all of its vertices are of same degree) are recognizable. To explore this further, we turn to Kelly.
Kelly’s Lemma

This section will be confined to graphs that satisfy the conjecture, such as finite, simple, undirected graphs with at least three vertices. There have been two general approaches toward the Reconstruction Conjecture, more directly, vertex reconstruction. One of the approaches involves reconstructing classes of graphs in hope that eventually enough classes will be found to generally include all graphs. In this paper, a class G will be reconstructible if each graph within that class is reconstructible. The other approach involves reconstructing parameters, in hope that eventually enough parameters will be reconstructed to propose a general statement about all parameter and the complete reconstruction of all graphs. A parameter, or any function defined on a class G of graphs will be reconstructible if, for each graph [pic]in the class G, it takes the same value on all reconstructions of the graph[pic]. One of the basic tools in the reconstruction of graphs is the counting technique that was developed by P.J. Kelly in 1957. Since we know that [pic] is reconstructible if it can be calculated from the [pic] we can look at Kelly’s Lemma to count the number of proper subgraphs of [pic] of any given type. Kelly’s Lemma asserts that for any graph [pic]with fewer vertices than[pic], the number of subgraphs of [pic] which are isomorphic to [pic] can be determined by summing the number of such subgraphs on each card and dividing the result by[pic]. Formally, the lemma is written and proven as follows.
Lemma 1. For any two graphs [pic] and [pic] such that [pic] [pic] is reconstructible.
Proof. Each subgraph of [pic] isomorphic to [pic] occurs in exactly [pic]of the vertex deleted subgraphs [pic] .
[pic]
If [pic] is a subgraph of [pic] and [pic] is isomorphic to[pic], then [pic] occurs in [pic] of the graphs[pic]. Specifically, [pic] would be a subgraph of those vertex-deleted subgraphs where [pic] is not in [pic] From this identity, it is obvious that since the right-hand side is clearly reconstructible, then so too must the left-hand side be. Furthermore, from Kelly’s lemma [pic] can be determined for any [pic]. As a consequence of this, two graphs who have the same deck must also have the same number of vertices, the same number of edges, and the same number of subgraphs of every type (i.e. same [pic] for all [pic] with [pic]). From his own lemma in regards to the Reconstruction Conjecture, Kelly also proposed the following ideas.
Corollary 1. For any two graphs [pic] and [pic]such that[pic]the number of subgraphs of [pic] that are isomorphic to [pic] and include a given vertex [pic] is reconstructible.
Proof. This number would just be [pic]
Corollary 2. The number of edges and the degree sequence are reconstructible.
Proof. Taking [pic]. Then the number of subgraphs of [pic] isomorphic to [pic] must be the edge set of [pic], or [pic]. From this we then known that

[pic]
[pic]
[pic]
Thus, is can be observed that Kelly’s lemma implies that the number of edges is determined by the deck.
Theorem 2. Regular graphs are reconstructible.
Proof. Let [pic] be a regular graph with more than three vertices, and let [pic] be the vertex-deleted subgraphs of[pic]. From definition, it is know that each of the subgraphs is missing one of the vertices in the graph[pic]. Since [pic] is a regular graph, each of the vertices are of same degree, [pic]. Observing each of the [pic] subgraphs, a single vertex can be inserted to replace the vertex that had been deleted. Next, edges can be replaced from the inserted vertex to any of the vertices in[pic], which have degree[pic]. This action is done until all the vertices have degree[pic]. So, by definition, [pic] is reconstructed. Kelly also proposes that (through applying his lemma) that disconnected graphs and trees are reconstructible. More information on this can be found in the literature referenced in this paper.
Conclusions

While only the basics of the Reconstruction Conjecture have been outlined in this paper, there has been substantial work on the current state of the conjecture. Beginning as a mere exercise question, the Reconstruction conjecture has evolved into one of the top unsolved problems in Graph Theory. Other subgraph counting methods have been proposed from renowned academics, such as the one given by Greenwell and Hemminger – which can be found in the referenced literature. Even an expansion of Kelly’s Lemma has been proposed by Kocay to include spanning subgraphs (which Kelly didn’t account for in his lemma). The Graph Reconstruction Conjecture has even led to other related mathematical problems, such as Graph Reconstruction Numbers, The Legitimate Deck Problem, and The problem of k-reconstruction. Overall, the general conjecture still remains unsolved, however, computer technology has allowed for greater finite testing of the conjecture which could eventually lead to the discovery of a general case for all graphs

References

[1] J.A. Bondy and R.L. Hemminger, Graph reconstruction - a survey. Journal of Graph Theory 1(1977),

227-268.

[2] J.A.Bondy, A graph reconstruction manual, Surveys in Combinatorics, LMS-Lecture Note Series

166(1991), 221-252.