Let $\Gamma$ be a connected graph. By (Kleitman-West, 1991),
if every vertex of $\Gamma$ has degree $\geq 3$, then $\Gamma$ has a spanning
tree with $\geq n/4+2$ leaves, where $n$ is the number of vertices of $\Gamma$.


It is relatively forward (though not completely trivial)
to deduce that, if every vertex of $\Gamma$ has
degree $\geq 2$, then $\Gamma$ has a spanning
tree with $\geq n/4+2$ leaves, where $n$ is the number of vertices of
$\Gamma$ of degree $\geq 3$.


Question: can the assumption on the degree of all vertices be dropped
altogether? That is, is it true that every connected graph $\Gamma$
with $n$ vertices of degree $\geq 3$ has a spanning tree with
$\geq n/4+2$ leaves? If not, can you give a counterexample?




---


Note 1:
The one case in doubt is that where there is exactly one vertex of degree $1$.
All other cases follow from (Bankevich-Karpov, 2011), which gives the lower
bound $\geq m/4+3/2$, where $m$ is the number of vertices of $\Gamma$ of degree
not $2$. Alternatively, one may reduce the general problem to the case
where exactly one vertex has degree $1$ as follows: given two vertices
$v\_1$, $v\_2$ of degree $1$, we may identify them (not changing the number of
vertices
of degree $\geq 3$ thereby) and apply the bound we are proving, recursively
(since the number of vertices of degree $1$ has decreased); if the spanning
tree contains the new vertex $v$ as a leaf, it is valid as a spanning tree
of the original graph; if it contains $v$ as an internal vertex, we
separate $v$ again into $v\_1$ and $v\_2$ (thus increasing the number of leaves
by $2$), and find that we have two trees, covering all vertices of $\Gamma$;
there is some edge of $\Gamma$ connecting them, and we may add it at a cost
of at most $2$ leaves.


Note 2: It obviously follows from Bankevich-Karpov that, when there is exactly one vertex of degree $1$, the bound $\geq n/4+7/4$ holds. It then follows
from (Karpov, 2012) that a counterexample to $\geq n/4 + 2$ would need
to have no vertices of degree $>3$.



Spanning trees: the last darn $1/4$
Consider connected $G$ with $n$ vertices of degree $\ge 3$ and exactly one vertex $v$ of degree 1. Take an extra copy $G'$ of $G$ with $v'$ being its vertex of degree 1.


Now identify $v$ and $v'$ to make a new graph $H$ which has $2n$ vertices of degree $\ge 3$ and no vertices of degree 1. The identified $v=v'$ has become a cut-vertex of degree 2. By the previous theorems, $H$ has a spanning tree with at least $2n/4+2$ leaves, and so at least $n/4+1$ leaves on one side of the cut. $v=v'$ isn't one of these leaves since it is a cut-vertex. Now take this spanning tree back to $G$ and $G'$. The side, say $G$, which had $n/4+1$ leaves in $H$ now has the extra leaf $v$, making $n/4+2$ leaves.


