Vignettes. Part 5.

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

approximationtoinfiniteregulartree

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 \aleph_0 neighbors at each vertex. (This is what the ” \aleph_0-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 rayfull 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
This entry was posted in expository, Higher trees, Mathematics, Olds, Research. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s