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

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. E. Baumgartner, J. Malitz, and W. Reinhardt, Embedding trees in the rationals, Proc. Nat. Acad. Sci. USA 67 (1970), 1748-1753. MR 0314621 (47:3172)
  • [3] R. Halin, Simplicial decompositions of infinite graphs, in Advances in Graph Theory (B. Bollobás, ed.), North-Holland, 1978. MR 499113 (80a:05162)
  • [4] -, Über unendliche Wege in Graphen, Math. Ann. 157 (1964), 125-137. MR 0170340 (30:578)
  • [5] R. Laver, Better-quasi-ordering and a class of trees, Studies in foundations and combinatorics, Adv. Math. Suppl. Stud., vol. 1, 1978, pp. 31-48. MR 520553 (80c:06005)
  • [6] N. Robertson, P. D. Seymour, and R. Thomas, Excluding subdivisions of infinite cliques, submitted.
  • [7] P. D. Seymour and R. Thomas, Excluding infinite trees, Trans. Amer. Math. Soc. (to appear). MR 1079058 (93d:05131)
  • [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

American Mathematical Society