A counterexample to the reconstruction conjecture for locally finite trees

Abstract

Two graphs $G$ and $H$ are hypomorphic if there exists a bijection $\phi :V(G)\to V(H)$ such that $G-v\cong H-\phi (v)$ for each $v\in V(G)$. A graph $G$ is reconstructible if $H\cong 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.

19 pages, Colour figures