This preprint was accepted March 9, 2007
ABSTRACT:
We prove the following theorem: every connected graph with $k$
vertices of degree at least 4 and $m$ vertices of degree
3 has a spanning tree with at least $\lceil\frac{2}{5} \cdot k + \frac{2}{15} \cdot m\rceil$
leaves.
[Full text:
(.ps.gz)]