Graphs with homeomorphically irreducible spanning trees
Michael O. Albertson, David Monty Berman, Joan P. Hutchinson, Carsten Thomassen · Journal of Graph Theory · 1990
Abstract It is an NP‐complete problem to decide whether a graph contains a spanning tree with no vertex of degree 2. We show that these homeomorphically irreducible spanning trees are contained in all graphs with minimum degree at least c√n and in triangulations of the plane. They are nearly present in all graphs of diameter 2. They do not necessarily occur in r‐regular or r‐connected graphs.