FACTOID # 1: Idaho produces more milk than Iowa, Indiana and Illinois combined.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Reconstruction conjecture

Informally, the reconstruction problem of graph theory is about the following. Consider a finite graph G with vertices v1,...,vn. If someone gives you a deck of cards which shows all the subgraphs where one vertex is deleted, ie the graphs G-vi for all i, can you then find the original graph G?

For graphs on two vertices this fails. Indeed, there are exactly two graphs on two vertices, the single edge and two isolated vertices, each of which leads to the same deck of cards, namely to two cards showing each a single vertex. However, for graphs with at least three vertices it has been conjectured in 1942 by P. J. Kelly and S. M. Ulam that it is always possible to reconstruct the graph from its deck of cards.

More formally, the reconstruction conjecture states:

Let G and H be finite graphs with at least three vertices, and let there be a bijection σ:V(G) → V(H) such that G-v is isomorphic to H-σ(v) for every v ∈ V(G). Then G and H are isomorphic.

This theorem has been proved for some specific classes of graphs, such as unlabeled trees. However, the conjecture remains open for arbitrary graphs.

## References

• Nash-Williams, C.St.J.A., The Reconstruction Problem, Selected topics in graph theory, 205-236 (1978)

Results from FactBites:

 Reconstruction conjecture - Wikipedia, the free encyclopedia (436 words) Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. The conjecture has been verified for a number of infinite classes of graphs, such as regular graphs (graphs in which all vertices have the same number of edges attached to them). 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.
 TPS Standards for Reconstruction (273 words) Reconstruction will be used to depict vanished or non-surviving portions of a property when documentary and physical evidence is available to permit accurate reconstruction with minimal conjecture, and such reconstruction is essential to the public understanding of the property. Reconstruction of a landscape, building, structure, or object in its historic location will be preceded by a thorough archeological investigation to identify and evaluate those features and artifacts which are essential to an accurate reconstruction. Reconstruction will be based on the accurate duplication of historic features and elements substantiated by documentary or physical evidence rather than on conjectural designs or the availability of different features from other historic properties.
More results at FactBites »

Share your thoughts, questions and commentary here