Improved bounds for spanning trees with many leaves

It is known that graphs on nn vertices with minimum degree at least 3 have spanning trees with at least n/4+2n/4+2 leaves and that this can be improved to (n+4)/3(n+4)/3 for cubic graphs without the diamond K4−eK4−e as a subgraph. We generalize the second result by proving that every graph GG without diamonds and certain subgraphs called blossoms has a spanning tree with at least (n≥3(G)+4)/3(n≥3(G)+4)/3 leaves, where n≥3(G)n≥3(G) is the number of vertices with degree at least 3 in GG. We show that it is necessary to exclude blossoms in order to obtain a bound of the form n≥3(G)/3+cn≥3(G)/3+c. This bound is used to deduce new similar bounds.