Halin's conjecture on hypomorphic infinite graphs
Bondy–Murty, Graph Theory, Appendix A, item 3 · Reconstruction
Status disproved high confidence
Halin's conjecture is disproved by Bowler, Erde, Heinig, Lehner, and Pitz (2017). Their Theorem 1.6 constructs two hypomorphic infinite trees T and S with maximum degree 3 such that neither T embeds in S nor S embeds in T, providing an explicit counterexample to the statement that hypomorphic infinite graphs are each isomorphic to a subgraph of the other. The counterexample uses locally finite trees, and the paper explicitly identifies it as a negative answer to Halin's Problem 1.5, which is exactly the conjecture in question.
Cited literature (1)
-
Theorem 1.6 constructs two hypomorphic infinite trees with maximum degree three admitting no embedding in either direction, thereby refuting Halin's Problem 1.5 — which is exactly the conjecture that hypomorphic infinite graphs are each isomorphic to a subgraph of the other.
Reviewer notes. The counterexample addresses the exact statement as given: two hypomorphic locally finite trees (max degree 3) are constructed that are not each isomorphic to a subgraph of the other. The ar5iv rendering of the paper confirms Problem 1.5 is attributed to Halin and reads 'If G and H are hypomorphic, do there exist embeddings G↪H and H↪G?', matching bm-003 word-for-word. The editorial note in the French Bondy–Murty edition correctly anticipated this resolution. The related OPG record (reconstruction_conjecture) concerns the finite case, which remains open and is not affected by this result.
Context
Two graphs $G$ and $H$ are hypomorphic if there is a bijection $\varphi\colon V(G)\to V(H)$ with $G - v \cong H - \varphi(v)$ for every vertex $v$. For finite graphs the Reconstruction Conjecture asserts that hypomorphic graphs are isomorphic; this fails for infinite graphs, and Halin's conjecture is the natural weakening.
In the book: Exercise 4.2.10.
Related records in this index
This conjecture was absent from the Open Problem Garden and arXiv corpora; the records below are the nearest ones.
- Reconstruction conjecture — finite analogue
Editorial notes. Bowler, Erde, Heinig, Lehner and Pitz, 'A counterexample to the reconstruction conjecture for locally finite trees' (Bull. London Math. Soc. 49, 2017), state that their construction also answers a question of Halin; the status review should check whether it is this one.
Source
Théorie des graphes (J.A. Bondy, U.S.R. Murty; French edition by Frédéric Havet, 2025), Appendix A « Problèmes ouverts »
Item 3, book p. 626 (PDF p. 642) ·
https://inria.hal.science/hal-05211979v1 ·
PDF
English edition: J.A. Bondy, U.S.R. Murty, Graph Theory, GTM 244, Springer 2008, Appendix A.