Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



An end-faithful spanning tree counterexample

Authors: Paul Seymour and Robin Thomas
Journal: Proc. Amer. Math. Soc. 113 (1991), 1163-1171
MSC: Primary 05C05; Secondary 03E35
MathSciNet review: 1045600
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] J. E. Baumgartner, Results and independence proofs in combinatorial set theory, Ph.D. Thesis, University of California, 1970.
  • [2] J. Baumgartner, J. Malitz, and W. Reinhardt, Embedding trees in the rationals, Proc. Nat. Acad. Sci. U.S.A. 67 (1970), 1748–1753. MR 0314621
  • [3] R. Halin, Simplicial decompositions of infinite graphs, Ann. Discrete Math. 3 (1978), 93–109. Advances in graph theory (Cambridge Combinatorial Conf., Trinity Coll., Cambridge, 1977). MR 499113
  • [4] R. Halin, Über unendliche Wege in Graphen, Math. Ann. 157 (1964), 125–137 (German). MR 0170340
  • [5] 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
  • [6] N. Robertson, P. D. Seymour, and R. Thomas, Excluding subdivisions of infinite cliques, submitted.
  • [7] P. D. Seymour and Robin Thomas, Excluding infinite trees, Trans. Amer. Math. Soc. 335 (1993), no. 2, 597–630. MR 1079058, 10.1090/S0002-9947-1993-1079058-6
  • [8] J. Širáň, Coterminal forests and spanning trees in infinite graphs, Proceedings of the Cambridge Conference on Infinite Graphs 1989, submitted.
  • [9] C. Thomassen, Infinite connected graphs with no end-preserving spanning trees, manuscript, 1990.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C05, 03E35

Retrieve articles in all journals with MSC: 05C05, 03E35

Additional Information

Article copyright: © Copyright 1991 American Mathematical Society