Spanning trees with few leaves and branch vertices under degree conditions

A leaf of a tree is a vertex with degree 1 and a branch vertex of a tree is a vertex with degree at least 3 in the tree. In this paper, we give two sufficient conditions for graphs to have a spanning tree with few total bounded number of leaves and branch vertices. First, by restricting Fan-type degree condition to [Formula: see text] or [Formula: see text] of a graph [Formula: see text], we prove that a 2-connected graph [Formula: see text] satisfying [Formula: see text] for any two nonadjacent vertices [Formula: see text] and [Formula: see text] of every induced [Formula: see text] or [Formula: see text] in [Formula: see text] with [Formula: see text] has a spanning tree with the total number of leaves and branch vertices at most [Formula: see text]. Second, we prove that a connected [Formula: see text]-free graph [Formula: see text] with [Formula: see text] has a spanning tree with the total number of leaves and branch vertices at most [Formula: see text] for [Formula: see text]. Moreover, we give examples to show the low bounds of the above degree conditions are best possible.