Spanning Trees Whose Stems have a Few Leaves

Abstract

For a tree $T$, $Leaf(T)$ denotes the set of leaves of $T$, and $T–Leaf(T)$ is called the stem of $T$. For a graph $G$ and a positive integer $m$, ${\sigma }_m(G)$ denotes the minimum degree sum of $m$ independent vertices of $G$. We prove the following theorem: Let $G$ be a connected graph and $k\ge 2$ be an integer. If ${\sigma }_3(G)\ge |G|–2k+1$, then $G$ has a spanning tree whose stem has at most $k$ leaves.