An end-faithful spanning tree counterexample
HTML articles powered by AMS MathViewer
- by Paul Seymour and Robin Thomas PDF
- Proc. Amer. Math. Soc. 113 (1991), 1163-1171 Request permission
Abstract:
We find an infinitely-connected graph in which every spanning tree has a $2$-way infinite path. This disproves Halin’s well-known "end-faithful spanning tree" conjecture and also disproves a recent conjecture of Širáň.References
-
J. E. Baumgartner, Results and independence proofs in combinatorial set theory, Ph.D. Thesis, University of California, 1970.
- J. Baumgartner, J. Malitz, and W. Reinhardt, Embedding trees in the rationals, Proc. Nat. Acad. Sci. U.S.A. 67 (1970), 1748–1753. MR 314621, DOI 10.1073/pnas.67.4.1748
- R. Halin, Simplicial decompositions of infinite graphs, Ann. Discrete Math. 3 (1978), 93–109. MR 499113
- R. Halin, Über unendliche Wege in Graphen, Math. Ann. 157 (1964), 125–137 (German). MR 170340, DOI 10.1007/BF01362670
- Richard Laver, Better-quasi-orderings and a class of trees, Studies in foundations and combinatorics, Adv. in Math. Suppl. Stud., vol. 1, Academic Press, New York-London, 1978, pp. 31–48. MR 520553 N. Robertson, P. D. Seymour, and R. Thomas, Excluding subdivisions of infinite cliques, submitted.
- P. D. Seymour and Robin Thomas, Excluding infinite trees, Trans. Amer. Math. Soc. 335 (1993), no. 2, 597–630. MR 1079058, DOI 10.1090/S0002-9947-1993-1079058-6 J. Širáň, Coterminal forests and spanning trees in infinite graphs, Proceedings of the Cambridge Conference on Infinite Graphs 1989, submitted. C. Thomassen, Infinite connected graphs with no end-preserving spanning trees, manuscript, 1990.
Additional Information
- © Copyright 1991 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 113 (1991), 1163-1171
- MSC: Primary 05C05; Secondary 03E35
- DOI: https://doi.org/10.1090/S0002-9939-1991-1045600-8
- MathSciNet review: 1045600