# Reconstruction conjecture

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Reconstruction_conjecture
> Markdown URL: https://mediated.wiki/source/Reconstruction_conjecture.md
> Source: https://en.wikipedia.org/wiki/Reconstruction_conjecture
> Source revision: 1353006129
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Conjecture in graph theory

Unsolved problem in mathematics

Are graphs uniquely determined by their subgraphs?

[More unsolved problems in mathematics](/source/List_of_unsolved_problems_in_mathematics)

In [graph theory](/source/Graph_theory), informally, the **reconstruction conjecture** says that [graphs](/source/Graph_(discrete_mathematics)) are determined uniquely by their subgraphs. It is due to [Kelly](/source/Paul_Kelly_(mathematician))[1] and [Ulam](/source/Stanislaw_Ulam).[2][3]

## Formal statements

A graph and the associated deck of single-vertex-deleted subgraphs. Note some of the cards show isomorphic graphs.

Given a graph G = ( V , E ) {\displaystyle G=(V,E)} , a **vertex-deleted subgraph** of G {\displaystyle G} is a [subgraph](/source/Glossary_of_graph_theory#Subgraphs) formed by deleting exactly one vertex from G {\displaystyle G} . By definition, it is an [induced subgraph](/source/Induced_subgraph) of G {\displaystyle G} .

For a graph G {\displaystyle G} , the **deck of G**, denoted D ( G ) {\displaystyle D(G)} , is the [multiset](/source/Multiset) of isomorphism classes of all vertex-deleted subgraphs of G {\displaystyle G} . Each graph in D ( G ) {\displaystyle 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:

- **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.)

[Harary](/source/Frank_Harary)[4] suggested a stronger version of the conjecture:

- **Set Reconstruction Conjecture:** Any two graphs on at least four vertices with the same sets of vertex-deleted subgraphs are isomorphic.

Given a graph G = ( V , E ) {\displaystyle G=(V,E)} , an **edge-deleted subgraph** of G {\displaystyle G} is a [subgraph](/source/Glossary_of_graph_theory#Subgraphs) formed by deleting exactly one edge from G {\displaystyle G} .

For a graph G {\displaystyle G} , the **edge-deck of G**, denoted E D ( G ) {\displaystyle ED(G)} , is the [multiset](/source/Multiset) of all isomorphism classes of edge-deleted subgraphs of G {\displaystyle G} . Each graph in E D ( G ) {\displaystyle ED(G)} is called an **edge-card**.

- **Edge Reconstruction Conjecture:** (Harary, 1964)[4] Any two graphs with at least four edges and having the same edge-decks are isomorphic.

## Recognizable properties

In context of the reconstruction conjecture, a [graph property](/source/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](/source/Glossary_of_graph_theory) – The order of a graph G {\displaystyle G} , | V ( G ) | {\displaystyle |V(G)|} is recognizable from D ( G ) {\displaystyle D(G)} as the multiset D ( G ) {\displaystyle D(G)} contains each subgraph of G {\displaystyle G} created by deleting one vertex of G {\displaystyle G} . Hence | V ( G ) | = | D ( G ) | {\displaystyle |V(G)|=|D(G)|} [5]

- [Number of edges of the graph](/source/Glossary_of_graph_theory) – The number of edges in a graph G {\displaystyle G} with n {\displaystyle n} vertices, | E ( G ) | {\displaystyle |E(G)|} is recognizable. First note that each edge of G {\displaystyle G} occurs in n − 2 {\displaystyle n-2} members of D ( G ) {\displaystyle D(G)} . This is true by the definition of D ( G ) {\displaystyle D(G)} which ensures that each edge is included every time that each of the vertices it is incident with is included in a member of D ( G ) {\displaystyle D(G)} , so an edge will occur in every member of D ( G ) {\displaystyle D(G)} except for the two in which its endpoints are deleted. Hence, | E ( G ) | = ∑ q i n − 2 {\displaystyle |E(G)|=\sum {\frac {q_{i}}{n-2}}} where q i {\displaystyle q_{i}} is the number of edges in the *i*th member of D ( G ) {\displaystyle D(G)} .[5]

- Number of Subgraphs of order k < n {\displaystyle k<n} (Kelly's Lemma) - Generalizing the edge count strategy, we can say for some subgraph H {\displaystyle H} with k {\displaystyle k} vertices in G {\displaystyle G} with n {\displaystyle n} vertices, the number of times H {\displaystyle H} appears in G {\displaystyle G} (referred to as ( G H ) {\displaystyle {\binom {G}{H}}} ) is reconstructible. As every instance of H {\displaystyle H} in G will appear in exactly all the cards in which a vertex of H {\displaystyle H} is not removed, each distinct instance of H {\displaystyle H} will appear in n − k {\displaystyle n-k} cards. As such, ( G H ) = ∑ ( D i H ) n − k {\displaystyle {\binom {G}{H}}=\sum {\frac {\binom {D_{i}}{H}}{n-k}}} , where D i {\displaystyle D_{i}} is the i {\displaystyle i} th card. [5]

- [Degree sequence](/source/Degree_sequence) – The degree sequence of a graph G {\displaystyle G} is recognizable because the degree of every vertex is recognizable. To find the degree of a vertex v i {\displaystyle v_{i}} —the vertex absent from the *i*th member of D ( G ) {\displaystyle D(G)} —, we will examine the graph created by deleting it, G i {\displaystyle G_{i}} . This graph contains all of the edges not incident with v i {\displaystyle v_{i}} , so if q i {\displaystyle q_{i}} is the number of edges in G i {\displaystyle G_{i}} , then | E ( G ) | − q i = deg ⁡ ( v i ) {\displaystyle |E(G)|-q_{i}=\deg(v_{i})} . If we can tell the degree of every vertex in the graph, we can tell the degree sequence of the graph.[5]

- [(Vertex-)Connectivity](/source/Connectivity_(graph_theory)) – By definition, a graph is n {\displaystyle n} -vertex-connected when deleting any vertex creates a n − 1 {\displaystyle n-1} -vertex-connected graph; thus, if every card is a n − 1 {\displaystyle n-1} -vertex-connected graph, we know the original graph was n {\displaystyle n} -vertex-connected. We can also determine if the original graph was connected, as this is equivalent to having any two of the G i {\displaystyle G_{i}} being connected.[5]

- [Tutte polynomial](/source/Tutte_polynomial)

- [Characteristic polynomial](/source/Characteristic_polynomial)

- [Planarity](/source/Planar_graph)

- The number of [spanning trees](/source/Spanning_tree_(mathematics)) in a graph

- [Chromatic polynomial](/source/Chromatic_polynomial)

- Being a [perfect graph](/source/Perfect_graph) or an [interval graph](/source/Interval_graph), or certain other subclasses of perfect graphs[6]

## Verification

Both the reconstruction and set reconstruction conjectures have been verified for all graphs with at most 13 vertices by [Brendan McKay](/source/Brendan_McKay_(mathematician)).[7][8]

In a probabilistic sense, it has been shown by [Béla Bollobás](/source/B%C3%A9la_Bollob%C3%A1s) that almost all graphs are reconstructible.[9] This means that the probability that a randomly chosen graph on n {\displaystyle n} vertices is not reconstructible goes to 0 as n {\displaystyle 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).

- [Regular graphs](/source/Regular_graph)[10] - Regular Graphs are reconstructible by direct application of some of the facts that can be recognized from the deck of a graph. Given an n {\displaystyle n} -regular graph G {\displaystyle G} and its deck D ( G ) {\displaystyle D(G)} , 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 D ( G ) {\displaystyle D(G)} , G i {\displaystyle G_{i}} . This graph contains some number of vertices with a degree of n {\displaystyle n} and n {\displaystyle n} vertices with a degree of n − 1 {\displaystyle n-1} . We can add a vertex to this graph and then connect it to the n {\displaystyle n} vertices of degree n − 1 {\displaystyle n-1} to create an n {\displaystyle n} -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.[5]

- [Trees](/source/Tree_(graph_theory))[10]

- [Disconnected graphs](/source/Connected_graph)[10]

- [Unit interval graphs](/source/Unit_interval_graph) [6]

- [Separable graphs](/source/Separable_graph) without [end vertices](/source/Leaf_vertex)[11]

- [Maximal planar graphs](/source/Maximal_planar_graph)

- [Maximal outerplanar graphs](/source/Maximal_outerplanar_graph)

- [Outerplanar graphs](/source/Outerplanar_graph)

- [Critical blocks](https://en.wikipedia.org/w/index.php?title=Critical_blocks&action=edit&redlink=1)

## Reduction

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

## Duality

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

- [Digraphs](/source/Graph_(discrete_mathematics)#Directed_graph): Infinite families of non-reconstructible digraphs are known, including [tournaments](/source/Tournament_(mathematics)) (Stockmeyer[13]) and non-tournaments (Stockmeyer[14]). A tournament is reconstructible if it is not strongly connected.[15] A weaker version of the reconstruction conjecture has been conjectured for digraphs, see [new digraph reconstruction conjecture](/source/New_digraph_reconstruction_conjecture).

- [Hypergraphs](/source/Hypergraph), including all k-uniform hypergraphs for k>2 ([Kocay](/source/William_Lawrence_Kocay)[16]).

- [Infinite graphs](/source/Infinite_graph). If *T* is the tree where every vertex has [countably infinite](/source/Countably_infinite) degree, then the union of two disjoint copies of *T* is hypomorphic, but not isomorphic, to *T*.([Fisher](/source/Joseph_A._Fisher)[17]) [18][19]

- Locally finite graphs, which are graphs where every vertex has finite degree. The question of reconstructibility for locally finite infinite trees (the Harary-Schwenk-Scott conjecture from 1972) was a longstanding open problem until 2017, when a non-reconstructible tree of maximum degree 3 was found by Bowler et al.[20]

## See also

- [New digraph reconstruction conjecture](/source/New_digraph_reconstruction_conjecture)

- [Partial symmetry](/source/Partial_symmetry)

## Further reading

For further information on this topic, see the survey by [Nash-Williams](/source/Crispin_St._J._A._Nash-Williams).[21]

## References

1. **[^](#cite_ref-Kelly57_1-0)** Kelly, P. J., [A congruence theorem for trees](http://projecteuclid.org/getRecord?id=euclid.pjm/1103043674), *Pacific J. Math.* **7** (1957), 961–968.

1. **[^](#cite_ref-Ulam60_2-0)** Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960.

1. **[^](#cite_ref-3)** O'Neil, Peter V. (1970). ["Ulam's conjecture and graph reconstructions"](http://www.maa.org/programs/maa-awards/writing-awards/ulams-conjecture-and-graph-reconstructions). *Amer. Math. Monthly*. **77** (1): 35–43. [doi](/source/Doi_(identifier)):[10.2307/2316851](https://doi.org/10.2307%2F2316851). [JSTOR](/source/JSTOR_(identifier)) [2316851](https://www.jstor.org/stable/2316851).

1. ^ [***a***](#cite_ref-Harary64_4-0) [***b***](#cite_ref-Harary64_4-1) 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.

1. ^ [***a***](#cite_ref-Wall_5-0) [***b***](#cite_ref-Wall_5-1) [***c***](#cite_ref-Wall_5-2) [***d***](#cite_ref-Wall_5-3) [***e***](#cite_ref-Wall_5-4) [***f***](#cite_ref-Wall_5-5) Wall, Nicole. ["The Reconstruction Conjecture"](http://www.geocities.ws/kirstensmom1998/ulam.pdf) (PDF). Retrieved 2014-03-31.

1. ^ [***a***](#cite_ref-rim_6-0) [***b***](#cite_ref-rim_6-1) von Rimscha, M.: Reconstructibility and perfect graphs. *Discrete Mathematics* **47**, 283–291 (1983)

1. **[^](#cite_ref-McKay97_7-0)** McKay, B. D., Small graphs are reconstructible, *Australas. J. Combin.* **15** (1997), 123–126.

1. **[^](#cite_ref-8)** [McKay, Brendan](/source/Brendan_McKay_(mathematician)) (2022). "Reconstruction of Small Graphs and Digraphs". *Austras. J. Combin*. **83**: 448–457. [arXiv](/source/ArXiv_(identifier)):[2102.01942](https://arxiv.org/abs/2102.01942).

1. **[^](#cite_ref-Bollobas90_9-0)** Bollobás, B., Almost every graph has reconstruction number three, *J. Graph Theory* **14** (1990), 1–4.

1. ^ [***a***](#cite_ref-h74_10-0) [***b***](#cite_ref-h74_10-1) [***c***](#cite_ref-h74_10-2) Harary, F. (1974), "A survey of the reconstruction conjecture", *Graphs and Combinatorics*, [Lecture Notes in Mathematics](/source/Lecture_Notes_in_Mathematics), vol. 406, Springer, pp. 18–28, [doi](/source/Doi_(identifier)):[10.1007/BFb0066431](https://doi.org/10.1007%2FBFb0066431), [ISBN](/source/ISBN_(identifier)) [978-3-540-06854-9](https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-06854-9)

1. **[^](#cite_ref-Bondy_11-0)** Bondy, J.-A. (1969). ["On Ulam's conjecture for separable graphs"](https://doi.org/10.2140%2Fpjm.1969.31.281). *Pacific J. Math*. **31** (2): 281–288. [doi](/source/Doi_(identifier)):[10.2140/pjm.1969.31.281](https://doi.org/10.2140%2Fpjm.1969.31.281).

1. **[^](#cite_ref-yang_12-0)** Yang Yongzhi:The reconstruction conjecture is true if all 2-connected graphs are reconstructible. *Journal of graph theory* **12**, 237–243 (1988)

1. **[^](#cite_ref-Stockmeyer77_13-0)** Stockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, *J. Graph Theory* **1** (1977), 19–25.

1. **[^](#cite_ref-Stockmeyer81_14-0)** Stockmeyer, P. K., A census of non-reconstructable digraphs, I: six related families, *J. Combin. Theory Ser. B* **31** (1981), 232–239.

1. **[^](#cite_ref-HararyPalmer_15-0)** Harary, F. and Palmer, E., On the problem of reconstructing a tournament from sub-tournaments, *Monatsh. Math.* **71** (1967), 14–23.

1. **[^](#cite_ref-Kocay87_16-0)** Kocay, W. L., A family of nonreconstructible hypergraphs, *J. Combin. Theory Ser. B* **42** (1987), 46–63.

1. **[^](#cite_ref-Fisher69_17-0)** Fisher, Joshua, A counterexample to the countable version of a conjecture of Ulam, *J. Combin. Theory* **7 (4)** (1969), 364–365.

1. **[^](#cite_ref-18)** Fisher, J.; [Graham, R. L.](/source/Ronald_Graham); Harary, F. (1972). "A simpler counterexample to the reconstruction conjecture for denumerable graphs". *Journal of Combinatorial Theory, Series B*. **12** (2): 203–204.

1. **[^](#cite_ref-19)** Nash-Williams, C. St. J. A.; Hemminger, Robert (3 December 1991). ["Reconstruction of infinite graphs"](https://www.sciencedirect.com/science/article/pii/0012365X91903383/pdf?md5=fd99dc0796c81d8351f912d3d86b7d5c&pid=1-s2.0-0012365X91903383-main.pdf) (PDF). *Discrete Mathematics*. **95** (1): 221–229. [doi](/source/Doi_(identifier)):[10.1016/0012-365X(91)90338-3](https://doi.org/10.1016%2F0012-365X%2891%2990338-3).

1. **[^](#cite_ref-20)** Bowler, N., Erde, J., Heinig, P., Lehner, F. and Pitz, M. (2017), A counterexample to the reconstruction conjecture for locally finite trees. Bull. London Math. Soc.. [doi](/source/Doi_(identifier)):[10.1112/blms.12053](https://doi.org/10.1112%2Fblms.12053)

1. **[^](#cite_ref-NashWilliams78_21-0)** [Nash-Williams, C. St. J. A.](/source/Crispin_St._J._A._Nash-Williams), The Reconstruction Problem, in *Selected topics in graph theory*, 205–236 (1978).

Authority control databases National United States Israel Other Yale LUX

---
Adapted from the Wikipedia article [Reconstruction conjecture](https://en.wikipedia.org/wiki/Reconstruction_conjecture) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Reconstruction_conjecture?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.