A counterexample to the reconstruction conjecture for locally finite trees
Nathan Bowler, Joshua Erde, Peter Heinig, Florian Lehner, Max F. Pitz · Bulletin of the London Mathematical Society · 2017
Two graphs G and H are hypomorphic if there exists a bijection φ : V ( G ) → V ( H ) such that G − v ≅ H − φ ( v ) for each v ∈ V ( G ) . A graph G is reconstructible if H ≅ G for all H hypomorphic to G. It is well known that not all infinite graphs are reconstructible. However, the Harary–Schwenk–Scott Conjecture from 1972 suggests that all locally finite trees are reconstructible. In this paper, we construct a counterexample to the Harary–Schwenk–Scott Conjecture. Our example also answers four other questions of Nash-Williams, Halin and Andreae on the reconstruction of infinite graphs.