SPANNING-TREES WITH MANY LEAVES

A connected graph having large minimum vertex degree must have a spanning tree with many leaves. In particular, let l(n, k) be the maximum integer m such that every connected n-vertex graph with minimum degree at least k has a spanning tree with at least m leaves. Then l(n, 3) greater-than-or-equal-to n/4 + 2, l(n, 4) greater-than-or-equal-to (2n + 8)/5, and l(n, k) less-than-or-equal-to n - 3 right-perpendicular-n/(k + 1)-left-perpendicular + 2 for all k. The lower bounds are proved by an algorithm that constructs a spanning tree with at least the desired number of leaves. Finally, l(n, k) greater-than-or-equal-to (1 - b ln k/k)n for large k, again proved algorithmically, where b is any constant exceeding 2.5.