# Spanning trees: the last darn $1/4$

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$$.

• What do you mean by a "spanning" tree? I thought a "spanning" tree is one that contains all the vertices of the original graph, but I guess it means something else here. – bof Oct 10 at 6:49
• Ah, sorry, leaves. – H A Helfgott Oct 10 at 6:53
• Have you tried contacting Karpov directly? – Timothy Chow Oct 10 at 22:51
• Yes, but he hasn't answered. Perhaps I don't have the right email address. – H A Helfgott Oct 11 at 5:47
• @TimothyChow I did. He promised to think about it. – Fedor Petrov Oct 14 at 11:23

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.