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 d T ( 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.