Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.

Formal statements

Given a graph G = (V,E), a vertex-deleted subgraph of G is a subgraph formed by deleting exactly one vertex from G. By definition, it is an induced subgraph of G. For a graph G, the deck of G, denoted D(G), is the multiset of isomorphism classes of all vertex-deleted subgraphs of G. Each graph in D(G) is called a card. Two graphs that have the same deck are said to be hypomorphic. With these definitions, the conjecture can be stated as: Harary suggested a stronger version of the conjecture: Given a graph G = (V,E), an edge-deleted subgraph of G is a subgraph formed by deleting exactly one edge from G. For a graph G, the edge-deck of G, denoted ED(G), is the multiset of all isomorphism classes of edge-deleted subgraphs of G. Each graph in ED(G) is called an edge-card.

Recognizable properties

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:

Verification

Both the reconstruction and set reconstruction conjectures have been verified for all graphs with at most 13 vertices by Brendan McKay. In a probabilistic sense, it has been shown by Béla Bollobás that almost all graphs are reconstructible. This means that the probability that a randomly chosen graph on n vertices is not reconstructible goes to 0 as n goes to infinity. 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.

Reconstructible graph families

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

Reduction

The reconstruction conjecture is true if all 2-connected graphs are reconstructible.

Duality

The vertex reconstruction conjecture obeys the duality that if G can be reconstructed from its vertex deck D(G), then its complement G' can be reconstructed from D(G') as follows: Start with D(G'), take the complement of every card in it to get D(G), use this to reconstruct G, then take the complement again to get G'. 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.

Other structures

It has been shown that the following are not in general reconstructible: