Spanning trees with constraints on the leaf degree Original Research Article

Let T be a tree and m be a positive integer. The leaf degree of a vertex x∈V(G) is defined as the number of end-vertices in T adjacent to x, and it is denoted by leafTx. (If x is an end-vertex of T with at least three vertices, then leafTx=0.) We prove that a connected graph G has a spanning tree T such that for any vertex x of T, leafTx⩽m if and only if for every nonempty subset S of V(G), the number of isolated vertices of G−S does not exceed (m+1)|S|−1.