Spanning Trees with many Leaves: New Lower Bounds in Terms of the Number of Vertices of Degree 3 and at Least 4.

It is proved that every connected graph with s vertices of degree 3 and t vertices of degree at least 4 has a spanning tree with $ \frac{2}{5}t+\frac{1}{5}s+\alpha $ leaves, where $ \alpha \geq \frac{8}{5} $. Moreover, α ≥ 2 for all graphs, except for three exclusions. All exclusions are regular graphs of degree 4, and they are explicitly described in the paper. An infinite series of graphs containing only vertices of degree 3 and 4, for which the maximal number of leaves in a spanning tree is equal to $ \frac{2}{5}t+\frac{1}{5}s+2 $, is presented. Therefore it is proved that the bound is tight. Bibliography: 12 titles. [ABSTRACT FROM AUTHOR]