Degree Conditions and Degree Bounded Trees

In this paper, we give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and A⊆V(G). We denote by σk(A) the minimum value of the degree sum in G of any k pairwise nonadjacent vertices of A, and by w(G−A) the number of components of the subgraph G−A of G induced by V(G)−A. Our main results are the following: (i) If σk(A)⩾|G|−1, then G contains a tree T with maximum degree ⩽k and A⊆V(T). (ii) If σk−w(G−A)(A)⩾|A|−1, then G contains a spanning tree T with dT(x)⩽k for any x∈A. These are generalizations of the result by S. Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Seminar Univ. Humburg 43 (1975) 263-267] and degree conditions are sharp.