Reconstruction conjecture

Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs.

It is due to Kelly[1] and Ulam.

is a subgraph formed by deleting exactly one vertex from

By definition, it is an induced subgraph of

, is the multiset of isomorphism classes of all vertex-deleted subgraphs of

Two graphs that have the same deck are said to be hypomorphic.

With these definitions, the conjecture can be stated as: Harary[4] suggested a stronger version of the conjecture: Given a graph

is a subgraph formed by deleting exactly one edge from

, is the multiset of all isomorphism classes of edge-deleted subgraphs of

In context of the reconstruction conjecture, a graph property is called recognizable if one can determine the property from the deck of a graph.

The following properties of graphs are recognizable: Both the reconstruction and set reconstruction conjectures have been verified for all graphs with at most 13 vertices by Brendan McKay.

[7][8] In a probabilistic sense, it has been shown by Béla Bollobás that almost all graphs are reconstructible.

[9] This means that the probability that a randomly chosen graph on

In fact, it was shown that not only are almost all graphs reconstructible, but in fact that the entire deck is not necessary to reconstruct them — almost all graphs have the property that there exist three cards in their deck that uniquely determine the graph.

The conjecture has been verified for a number of infinite classes of graphs (and, trivially, their complements).

[12] The vertex reconstruction conjecture obeys the duality that if

can be reconstructed from its vertex deck

Edge reconstruction does not obey any such duality: Indeed, for some classes of edge-reconstructible graphs it is not known if their complements are edge reconstructible.

It has been shown that the following are not in general reconstructible: For further information on this topic, see the survey by Nash-Williams.