The edge reconstruction conjecture for graphs

Abstract

In 1942 Kelly conjectured that any finite, simple, undirected graph having at least 3 vertices is uniquely determined by the multiset of all its subgraphs obtained by deleting a vertex and all edges adjacent to it. In 1964 Harary conjectured analogously that any graph having at least 4 edges is uniquely determined by all its subgraphs obtained by deleting a single edge, which is known as the edge reconstruction conjecture. Both conjectures are still open. In the first part of this thesis we will discuss some of the work done so far and provide some evidence in favour of the reconstruction conjectures. In the second part I will prove that a specific type of tridegreed graphs is edge-reconstructible, using techniques similar to those used by Myrvold, Ellingham and Hoffman to prove that any bidegreed graph is edge-reconstructible.