Infinite connected graphs with no end-preserving spanning trees. (English) Zbl 0753.05030

Thomassen, Carsten

J. Comb. Theory, Ser. B 54, No. 2, 322-324 (1992).

Summary: In 1964 R. Halin raised the question if every infinite connected graph \(G\) has a spanning tree \(T\) with the same structure as \(G\) in the sense that every end of \(G\) is represented by precisely one end of \(T\). We answer the question in the negative even for graphs of infinite connectivity (and hence with only one end). A negative answer was obtained independently by P. D. Seymour and R. Thomas and by P. Komjath.

MSC:

05C10	Planar graphs; geometric and topological aspects of graph theory
05C05	Trees
05C40	Connectivity

Keywords:

infinite connected graph; spanning tree; infinite connectivity

References:

[1]	Halin, R., Über unendliche Wege in Graphen, Math. Ann., 157, 125-137 (1964), Math. Rev. 30, #578 · Zbl 0125.11701
[2]	Polat, N., Aspects topologiques de la séparation dans les graphes infinit, Math. Z., 165, 171-191 (1979), Math. Rev. 80f: 005040 · Zbl 0387.05007
[3]	Polat, N., Topological aspects of infinite graphs, (Hahn, G.; Sabidussi, G.; Woodrow, R. E., Cycles and Rays (1990), Kluwer: Kluwer Dordrecht), 197-220 · Zbl 0705.05029
[4]	Thomassen, C., Infinite graphs, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory II. Selected Topics in Graph Theory II, Math. Rev. 876: 05045 (1983), Academic Press: Academic Press New York) · Zbl 0554.05021