Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7

We give a polynomial-time algorithm that constructs, in every connected $n$-vertex graph of minimum degree at least $7$, a spanning tree with at least $\frac{25200}{46189}n>0.5455n$ leaves. No bound specific to minimum degree $7$ was known: the best bound available for this class was $\frac{11}{21}n\approx 0.5238n$, inherited from Simarova’s theorem for minimum degree~$6$. The algorithm and its analysis are carried out for an arbitrary minimum degree $\delta$, and yield a recursion that gives an explicit lower bound on the number of leaves for every $\delta$. The resulting bounds improve all previously known ones for every $\delta \ge 7$; for $\delta =8,9,10$ they are $0.5850n$, $0.6151n$ and $0.6413n$, and they are tabulated for $\delta \le 25$ at the end of the paper.