Constructing a spanning tree with many leaves

It was shown by Griggs and Wu that a graph of minimal degree 4 on n vertices has a spanning tree with at least frac25 frac{2}{5} n leaves, which is asymptomatically the best possible bound for this class of graphs. In this paper, we present a polynomial time algorithm that finds in any graph with k vertices of degree greater than or equal to 4 and k′ vertices of degree 3 a spanning tree with [ frac25 ·k + frac215 ·k￠ ] left[ {frac{2}{5} cdot k + frac{2}{{15}} cdot k'} right] leaves.