A bound on the number of leaves in a spanning tree of a connected graph of minimum degree 6 (Q2632551)

Given a graph $G$, let $v(G)$ denote the number of vertices in $G$ and let $n(G)$ denote the maximum number of leaves in a spanning tree of $G$. Then let $t(G) = \frac{n(G)}{v(G)}$. The main result of this work shows the following. \par Theorem. If $G$ is a connected graph with minimum degree $6$, then $G$ has $t(G) \geq \frac{11}{21}$. \par It is observed that this bound is not tight but the best known upper lower bound. \par The proof is constructive, building the desired spanning tree in steps by adding new vertices to the tree and removing old leaves from the previous tree. This has been called the ``dead vertices'' method. The resulting tree is then shown to have the desired number of leaves by counting based on the steps in the construction.