Lower Bounds on the Number of Leaves in Spanning Trees.

Let G be a connected graph on n ≥ 2 vertices with girth at least g such that the length of a maximal chain of successively adjacent vertices of degree 2 in G does not exceed k ≥ 1. Denote by u(G) the maximum number of leaves in a spanning tree of G. We prove that u(G) ≥ αg,k(υ(G) − k − 2) + 2 where αg,1=g+124g+12+1<inline-graphic></inline-graphic> and αg,k=12k+2<inline-graphic></inline-graphic> for k ≥ 2. We present an infinite series of examples showing that all these bounds are tight. [ABSTRACT FROM AUTHOR]