|Unsolved problem in mathematics:
Are graphs uniquely determined by their subgraphs?
(more unsolved problems in mathematics)
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 - Regular Graphs are reconstructible by direct application of some of the facts that can be recognized from the deck of a graph. Given an -regular graph and its deck , we can recognize that the deck is of a regular graph by recognizing its degree sequence. Let us now examine one member of the deck , . This graph contains some number of vertices with a degree of and vertices with a degree of . We can add a vertex to this graph and then connect it to the vertices of degree to create an -regular graph which is isomorphic to the graph which we started with. Therefore, all regular graphs are reconstructible from their decks. A particular type of regular graph which is interesting is the complete graph.
- Disconnected graphs
- Unit interval graphs 
- Separable graphs without end vertices
- Maximal planar graphs
- Maximal outerplanar graphs
- Outerplanar graphs
- Critical blocks
|This section does not cite any 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:
- Order of the graph – The order of a graph , is recognizable from as the multiset contains each subgraph of created by deleting one vertex of . Hence 
- Number of edges of the graph – The number of edges in a graph with vertices, is recognizable. First note that each edge of occurs in members of . This is true by the definition of which ensures that each edge is included every time that each of the vertices it is incident with is included in a member of , so an edge will occur in every member of except for the two in which its endpoints are deleted. Hence, where is the number of edges in the ith member of 
- Degree sequence – The degree sequence of a graph is recognizable because the degree of every vertex is recognizable. To find the degree of a vertex , we will examine the graph created by deleting it, . This graph contains all of the edges not incident with ,so if is the number of edges in and is the number of edges in , then . If we can tell the degree of every vertex in the graph, we can tell the degree sequence of the graph.
- Tutte polynomial
- The types of spanning trees in a graph
- Chromatic polynomial
- Being a perfect graph or an interval graph, or certain 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.
- O'Neil, Peter V. (1970). "Ulam's conjecture and graph reconstructions". Amer. Math. Monthly 77: 35–43. doi:10.2307/2316851.
- 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, Springer, pp. 18–28, doi:10.1007/BFb0066431
- Wall, Nicole. "The Reconstruction Conjecture" (PDF). Retrieved 2014-03-31.
- von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)
- Bondy, J.-A. (1969). "On Ulam's conjecture for separable graphs". Pacific J. Math. 31: 281–288. doi:10.2140/pjm.1969.31.281.
- 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).