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 -way infinite path. This disproves Halin's well-known "end-faithful spanning tree" conjecture and also disproves a recent conjecture of Širáň.

**[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.

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1991-1045600-8

Article copyright:
© Copyright 1991
American Mathematical Society