Graphs with homeomorphically irreducible spanning trees

Abstract

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.