Jennifer Chamberlain: The Reconstruction Conjecture

Abstract:

The Reconstruction Conjecture claims that if a graph is finite, simple and undirected, and contains at least three vertices, it can be determined (up to isomorphism) by the multiset of all its maximal vertex-proper subgraphs. The Conjecture has been proven for certain classes of graphs, but is not yet proven in general.

In this thesis, we first describe some of the proven cases, such as disconnected graphs, trees, and some cases of separable graphs (though separable graphs are not proven, in general, to be reconstructible in this thesis or, so far as we are aware, elsewhere). We will also consider a special case of connected, nonseparable graphs, where all but a few vertices have the same degree. For this type of graph, we prove the case where only one vertex differs in degree entirely, and we also prove, except in some special cases, the case where two vertices differ in degree.