Lower Bounds on the Number of Leaves in Spanning Trees

Abstract

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 \( {\alpha}_{g,1}=\frac{\left[\frac{g+1}{2}\right]}{4\left[\frac{g+1}{2}\right]+1} \) and \( {\alpha}_{g,k}=\frac{1}{2k+2} \) for k ≥ 2. We present an infinite series of examples showing that all these bounds are tight.