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

Sogol Jahanbekam

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.5455\…