Arguably the simplest non-trivial example of an unlabelled simple undirected graph which is not reconstructible from its vertex-deleted subgraphs is the -regular tree, illustrated *in parts *by

Needfull to say: that you only see *five *neighbors at each vertex is *an arbitrary concession to the finiteness of the technological means used to produce this picture. *In reality, this tree has precisely * neighbors at each vertex. *(This is what the ” -regular ” above means.)

Needless to say, this is not a rayless tree. From a constructivist point of view, one might be inclined to say that it is a ray*full *tree.

###### (The *first, *but not the simplest, example, which unlike the above has the virtue of being almost *locally* *finite*, but is much less symmetric than the above and seems never to have been *illustrated* anywhere in the published literature, was published by Joshua Fisher in 1969; *locally finite* essentially means that the tree does not have any vertex with infinitely-many neighbors; it took almost fifty years until a *locally finite *example was published.)

Advertisements