Spanning trees whose stems are spiders (Q897247): Difference between revisions

The stem of a tree \(T\) is the graph obtained from \(T\) be deleting its leaves; a spider is a tree with at most one vertex with degree greater than two. Let \(G\) be a graph; it is proved here that if the minimal degree sum of four vertices of \(G\), such that the distance between any two of them is at least four, is at least \(|G|-5\), then \(G\) has a spanning tree whose stem is a spider. A counterexample shows that this condition is optimal. As a corollary, if the minimal degree of vertices of \(|G|\) is at least \((|G|-5)/4\), then \(G\) has a spannign tree whose stem is a spider.