|Are graphs uniquely determined by their subgraphs?|
For a graph , the deck of G, denoted , is the multiset of all vertex-deleted subgraphs of . Each graph in 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:
- Reconstruction Conjecture: Any two hypomorphic graphs on at least three vertices are isomorphic.
(The requirement that the graphs have at least three vertices is necessary because both graphs on two vertices have the same decks.)
- Set Reconstruction Conjecture: Any two graphs on at least four vertices with the same sets of vertex-deleted subgraphs are isomorphic.
Given a graph , an edge-deleted subgraph of is a subgraph formed by deleting exactly one edge from .
For a graph , the edge-deck of G, denoted , is the multiset of all edge-deleted subgraphs of . Each graph in is called an edge-card.
- Edge Reconstruction Conjecture: (Harary, 1964) Any two graphs with at least four edges and having the same edge-decks are isomorphic.
In a probabilistic sense, it has been shown (Bollobás) that almost all graphs are reconstructible. This means that the probability that a randomly chosen graph on vertices is not reconstructible goes to 0 as 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.
- Regular graphs
- Disconnected graphs
- Unit interval graphs 
- Separable graphs without end vertices
- Maximal planar graphs
- Maximal outerplanar graphs
- Outer planar graphs
- Critical blocks
|This section does not cite any references or sources. (August 2009)|
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:
- Degree sequence
- Tutte polynomial
- The types of spanning trees in a graph
- Chromatic polynomial
- Being a perfect graph or an interval graph, or some other subclasses of perfect graphs 
The reconstruction conjecture is true if all 2-connected graphs are reconstructible 
It has been shown that the following are not in general reconstructible:
- Digraphs: Infinite families of non-reconstructible digraphs are known, including tournaments (Stockmeyer) and non-tournaments (Stockmeyer). A tournament is reconstructible if it is not strongly connected. A weaker version of the reconstruction conjecture has been conjectured for digraphs, see New digraph reconstruction conjecture.
- Hypergraphs (Kocay).
- Infinite graphs. Let T be a tree on an infinite number of vertices such that every vertex has infinite degree. The counterexample is T and 2T. The question of reconstructibility for locally finite infinite graphs is still open.
- Kelly, P. J., A congruence theorem for trees, Pacific J. Math., 7 (1957), 961–968.
- Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960.
- Harary, F., On the reconstruction of a graph from a collection of subgraphs. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52.
- McKay, B. D., Small graphs are reconstructible, Australas. J. Combin., 15 (1997), 123–126.
- Bollobás, B., Almost every graph has reconstruction number three, J. Graph Theory, 14 (1990), 1–4.
- Harary, F. (1974), "A survey of the reconstruction conjecture", A survey of the reconstruction conjecture, Graphs and Combinatorics. Lecture Notes in Mathematics 406 406, Springer, pp. 18–28, doi:10.1007/BFb0066431
- von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)
- Yang Yongzhi:The reconstruction conjecture is true if all 2-connected graphs are reconstructible. Journal of graph theory 12, 237–243 (1988)
- Stockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory, 1 (1977), 19–25.
- Stockmeyer, P. K., A census of non-reconstructable digraphs, I: six related families, J. Combin. Theory Ser. B, 31 (1981), 232–239.
- Harary, F. and Palmer, E., On the problem of reconstructing a tournament from sub-tournaments, Monatsh. Math., 71 (1967), 14–23.
- Kocay, W. L., A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B, 42 (1987), 46–63.
- Nash-Williams, C. St. J. A., The Reconstruction Problem, in Selected topics in graph theory, 205–236 (1978).