Reconstruction conjecture

<h2 id="formal-statements">Formal statements</h2>

Given a graph 
 
 
 
 G
 =
 (
 V
 ,
 E
 )
 
 
 {\displaystyle G=(V,E)}
 
, a vertex-deleted subgraph of 
 
 
 
 G
 
 
 {\displaystyle G}
 
 is a <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraph</a> formed by deleting exactly one vertex from 
 
 
 
 G
 
 
 {\displaystyle G}
 
. By definition, it is an <a href="/facts/Induced_subgraph/G3EUC0MQ">induced subgraph</a> of 
 
 
 
 G
 
 
 {\displaystyle G}
 
.
For a graph 
 
 
 
 G
 
 
 {\displaystyle G}
 
, the deck of G, denoted 
 
 
 
 D
 (
 G
 )
 
 
 {\displaystyle D(G)}
 
, is the <a href="/facts/Multiset/bPFJGMDo">multiset</a> 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:

<ul><li>Reconstruction Conjecture: Any two hypomorphic graphs on at least three vertices are isomorphic.</li></ul>
(The requirement that the graphs have at least three vertices is necessary because both graphs on two vertices have the same decks.)
<a href="/facts/Frank_Harary/3J2P7l4w">Harary</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> suggested a stronger version of the conjecture:

<ul><li>Set Reconstruction Conjecture: Any two graphs on at least four vertices with the same sets of vertex-deleted subgraphs are isomorphic.</li></ul>
Given a graph 
 
 
 
 G
 =
 (
 V
 ,
 E
 )
 
 
 {\displaystyle G=(V,E)}
 
, an edge-deleted subgraph of 
 
 
 
 G
 
 
 {\displaystyle G}
 
 is a <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraph</a> 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 <a href="/facts/Multiset/bPFJGMDo">multiset</a> 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.

<ul><li>Edge Reconstruction Conjecture: (Harary, 1964)<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> Any two graphs with at least four edges and having the same edge-decks are isomorphic.</li></ul>
<h2 id="recognizable-properties">Recognizable properties</h2>
In context of the reconstruction conjecture, a <a href="/facts/Graph_property/bjuIvgb1">graph property</a> is called recognizable if one can determine the property from the deck of a graph. The following properties of graphs are recognizable:

<ul><li><a href="/facts/Glossary_of_graph_theory/W0MqKkyE">Order of the graph</a> – 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)|}
 
 <a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li><a href="/facts/Glossary_of_graph_theory/W0MqKkyE">Number of edges of the graph</a> – 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 ith member of 
 
 
 
 D
 (
 G
 )
 
 
 {\displaystyle D(G)}
 
.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a></li>
<li><a href="/facts/Degree_sequence/LnFFpI8v">Degree sequence</a> – 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 ith 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.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a></li>
<li><a href="/facts/Connectivity_(graph_theory)/FSNjsYhz">(Vertex-)Connectivity</a> – 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.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a></li>
<li><a href="/facts/Tutte_polynomial/RMzCMxTQ">Tutte polynomial</a></li>
<li><a href="/facts/Characteristic_polynomial/7m8roDqo">Characteristic polynomial</a></li>
<li><a href="/facts/Planar_graph/plREagr9">Planarity</a></li>
<li>The types of <a href="/facts/Spanning_tree_(mathematics)/qQPN9taR">spanning trees</a> in a graph</li>
<li><a href="/facts/Chromatic_polynomial/dvr4Hyz9">Chromatic polynomial</a></li>
<li>Being a <a href="/facts/Perfect_graph/wcPdhjG9">perfect graph</a> or an <a href="/facts/Interval_graph/oLwYI3uT">interval graph</a>, or certain other subclasses of perfect graphs<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a></li></ul>
<h2 id="verification">Verification</h2>
Both the reconstruction and set reconstruction conjectures have been verified for all graphs with at most 13 vertices by <a href="/facts/Brendan_McKay_(mathematician)/zEvgN64q">Brendan McKay</a>.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a><a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
In a probabilistic sense, it has been shown by <a href="/facts/B%C3%A9la_Bollob%C3%A1s/9T1eot5o">Béla Bollobás</a> that almost all graphs are reconstructible.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> 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.

<h3>Reconstructible graph families</h3>
The conjecture has been verified for a number of infinite classes of graphs (and, trivially, their complements).

<ul><li><a href="/facts/Regular_graph/j9dSoLE6">Regular graphs</a><a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> - 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.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a></li>
<li><a href="/facts/Tree_(graph_theory)/TCWk4Joy">Trees</a><a class="footnote-ref" id="fnref:16" href="#fn:16">16</a></li>
<li><a href="/facts/Connected_graph/FSNjsYhz">Disconnected graphs</a><a class="footnote-ref" id="fnref:17" href="#fn:17">17</a></li>
<li><a href="/facts/Unit_interval_graph/56tB4Vah">Unit interval graphs</a> <a class="footnote-ref" id="fnref:18" href="#fn:18">18</a></li>
<li><a href="/facts/Separable_graph/FSNjsYhz">Separable graphs</a> without <a href="/facts/Leaf_vertex/WhlWmL3o">end vertices</a><a class="footnote-ref" id="fnref:19" href="#fn:19">19</a></li>
<li><a href="/facts/Maximal_planar_graph/plREagr9">Maximal planar graphs</a></li>
<li><a href="/facts/Maximal_outerplanar_graph/FrAgUpcV">Maximal outerplanar graphs</a></li>
<li><a href="/facts/Outerplanar_graph/FrAgUpcV">Outerplanar graphs</a></li>
<li>Critical blocks</li></ul>
<h2 id="reduction">Reduction</h2>
The reconstruction conjecture is true if all 2-connected graphs are reconstructible.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>

<h2 id="duality">Duality</h2>
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.

<h2 id="other-structures">Other structures</h2>
It has been shown that the following are not in general reconstructible:

<ul><li><a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">Digraphs</a>: Infinite families of non-reconstructible digraphs are known, including <a href="/facts/Tournament_(mathematics)/SVj5jWWE">tournaments</a> (Stockmeyer<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>) and non-tournaments (Stockmeyer<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>). A tournament is reconstructible if it is not strongly connected.<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a> A weaker version of the reconstruction conjecture has been conjectured for digraphs, see <a href="/facts/New_digraph_reconstruction_conjecture/JYMVMmUA">new digraph reconstruction conjecture</a>.</li>
<li><a href="/facts/Hypergraph/qIR2o2I3">Hypergraphs</a> (<a href="/facts/William_Lawrence_Kocay/PpGAlGtN">Kocay</a><a class="footnote-ref" id="fnref:24" href="#fn:24">24</a>).</li>
<li><a href="/facts/Infinite_graph/W0MqKkyE">Infinite graphs</a>. If T is the tree where every vertex has <a href="/facts/Countably_infinite/Wj4DmWPv">countably infinite</a> degree, then the union of two disjoint copies of T is hypomorphic, but not isomorphic, to T.<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a></li>
<li>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.<a class="footnote-ref" id="fnref:26" href="#fn:26">26</a></li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/New_digraph_reconstruction_conjecture/JYMVMmUA">New digraph reconstruction conjecture</a></li>
<li><a href="/facts/Partial_symmetry/c8NXPzqM">Partial symmetry</a></li></ul>
<h2 id="further-reading">Further reading</h2>
For further information on this topic, see the survey by <a href="/facts/Crispin_St._J._A._Nash-Williams/YY5uresp">Nash-Williams</a>.<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Kelly, P. J., A congruence theorem for trees, Pacific J. Math. 7 (1957), 961–968. <a href="http://projecteuclid.org/getRecord?id=euclid.pjm/1103043674" target="_blank">http://projecteuclid.org/getRecord?id=euclid.pjm/1103043674</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960. <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">O'Neil, Peter V. (1970). "Ulam's conjecture and graph reconstructions". Amer. Math. Monthly. 77 (1): 35–43. doi:10.2307/2316851. JSTOR 2316851. <a href="http://www.maa.org/programs/maa-awards/writing-awards/ulams-conjecture-and-graph-reconstructions" target="_blank">http://www.maa.org/programs/maa-awards/writing-awards/ulams-conjecture-and-graph-reconstructions</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">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. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">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. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Wall, Nicole. "The Reconstruction Conjecture" (PDF). Retrieved 2014-03-31. <a href="http://www.geocities.ws/kirstensmom1998/ulam.pdf" target="_blank">http://www.geocities.ws/kirstensmom1998/ulam.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Wall, Nicole. "The Reconstruction Conjecture" (PDF). Retrieved 2014-03-31. <a href="http://www.geocities.ws/kirstensmom1998/ulam.pdf" target="_blank">http://www.geocities.ws/kirstensmom1998/ulam.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Wall, Nicole. "The Reconstruction Conjecture" (PDF). Retrieved 2014-03-31. <a href="http://www.geocities.ws/kirstensmom1998/ulam.pdf" target="_blank">http://www.geocities.ws/kirstensmom1998/ulam.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Wall, Nicole. "The Reconstruction Conjecture" (PDF). Retrieved 2014-03-31. <a href="http://www.geocities.ws/kirstensmom1998/ulam.pdf" target="_blank">http://www.geocities.ws/kirstensmom1998/ulam.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983) <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">McKay, B. D., Small graphs are reconstructible, Australas. J. Combin. 15 (1997), 123–126. <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">McKay, Brendan (2022). "Reconstruction of Small Graphs and Digraphs". Austras. J. Combin. 83: 448–457. arXiv:2102.01942. <a href="/wiki/Brendan_McKay_(mathematician)" target="_blank">/wiki/Brendan_McKay_(mathematician)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Bollobás, B., Almost every graph has reconstruction number three, J. Graph Theory 14 (1990), 1–4. <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Harary, F. (1974), "A survey of the reconstruction conjecture", Graphs and Combinatorics, Lecture Notes in Mathematics, vol. 406, Springer, pp. 18–28, doi:10.1007/BFb0066431, ISBN 978-3-540-06854-9 <a href="978-3-540-06854-9" target="_blank">978-3-540-06854-9</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Wall, Nicole. "The Reconstruction Conjecture" (PDF). Retrieved 2014-03-31. <a href="http://www.geocities.ws/kirstensmom1998/ulam.pdf" target="_blank">http://www.geocities.ws/kirstensmom1998/ulam.pdf</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Harary, F. (1974), "A survey of the reconstruction conjecture", Graphs and Combinatorics, Lecture Notes in Mathematics, vol. 406, Springer, pp. 18–28, doi:10.1007/BFb0066431, ISBN 978-3-540-06854-9 <a href="978-3-540-06854-9" target="_blank">978-3-540-06854-9</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Harary, F. (1974), "A survey of the reconstruction conjecture", Graphs and Combinatorics, Lecture Notes in Mathematics, vol. 406, Springer, pp. 18–28, doi:10.1007/BFb0066431, ISBN 978-3-540-06854-9 <a href="978-3-540-06854-9" target="_blank">978-3-540-06854-9</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983) <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Bondy, J.-A. (1969). "On Ulam's conjecture for separable graphs". Pacific J. Math. 31 (2): 281–288. doi:10.2140/pjm.1969.31.281. <a href="https://doi.org/10.2140%2Fpjm.1969.31.281" target="_blank">https://doi.org/10.2140%2Fpjm.1969.31.281</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Yang Yongzhi:The reconstruction conjecture is true if all 2-connected graphs are reconstructible. Journal of graph theory 12, 237–243 (1988) <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Stockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory 1 (1977), 19–25. <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Stockmeyer, P. K., A census of non-reconstructable digraphs, I: six related families, J. Combin. Theory Ser. B 31 (1981), 232–239. <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Harary, F. and Palmer, E., On the problem of reconstructing a tournament from sub-tournaments, Monatsh. Math. 71 (1967), 14–23. <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Kocay, W. L., A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B 42 (1987), 46–63. <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Nash-Williams, C. St. J. A.; Hemminger, Robert (3 December 1991). "Reconstruction of infinite graphs" (PDF). Discrete Mathematics. 95 (1): 221–229. doi:10.1016/0012-365X(91)90338-3. <a href="https://www.sciencedirect.com/science/article/pii/0012365X91903383/pdf?md5=fd99dc0796c81d8351f912d3d86b7d5c&pid=1-s2.0-0012365X91903383-main.pdf" target="_blank">https://www.sciencedirect.com/science/article/pii/0012365X91903383/pdf?md5=fd99dc0796c81d8351f912d3d86b7d5c&pid=1-s2.0-0012365X91903383-main.pdf</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">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:10.1112/blms.12053 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Nash-Williams, C. St. J. A., The Reconstruction Problem, in Selected topics in graph theory, 205–236 (1978). <a href="/wiki/Crispin_St._J._A._Nash-Williams" target="_blank">/wiki/Crispin_St._J._A._Nash-Williams</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
</ol>

Reconstruction conjecture open-in-new

Reconstruction conjecture