A counterexample to the reconstruction conjecture for locally finite trees. Issue 4 (26th April 2017)

• Record Type: Journal Article
• Authors: Bowler, Nathan; Erde, Joshua; Heinig, Peter; Lehner, Florian; Pitz, Max
• Is Part Of: Bulletin of the London Mathematical Society. Volume 49:Issue 4(2017)
• Page Start: 630
• Page End: 648
• Publication Date: 2017-04-26
• Subjects: 05C60 -- 05C63 (primary); Mathematics -- Periodicals; 510
• DOI: 10.1112/blms.12053
• Languages: English
• ISSNs: 0024-6093

Abstract

Abstract: 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.