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

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

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

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