Abstract:
We prove that for every connected graph with girth at least $4$ and $s$ vertices of degree not $2$ there is a spanning tree with at least $\frac13(s-2)+2$ leaves. We describe series of examples showing that this bound is tight. This result, together with the bound for graphs with no limit on the girth (in such graphs one can construct a spanning tree with at least $\frac14(s-2)+2$ leaves) leads to the hypothesis that for a graph with girth at least $g$, there exists a spanning tree with at least $\frac{g-2}{2g-2}(s-2)+2$ leaves. We prove that this conjecture fails for $g\ge10$ and the bound cannot exceed $\frac7{16}s+\frac12$.
Key words and phrases:spanning tree, leaves, number of leaves.