14
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – bof Oct 10 at 6:49
  • $\begingroup$ Ah, sorry, leaves. $\endgroup$ – H A Helfgott Oct 10 at 6:53
  • $\begingroup$ Have you tried contacting Karpov directly? $\endgroup$ – Timothy Chow Oct 10 at 22:51
  • $\begingroup$ Yes, but he hasn't answered. Perhaps I don't have the right email address. $\endgroup$ – H A Helfgott Oct 11 at 5:47
  • $\begingroup$ @TimothyChow I did. He promised to think about it. $\endgroup$ – Fedor Petrov Oct 14 at 11:23
12
+100
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That's very nice. Is it a standard argument? $\endgroup$ – H A Helfgott Oct 15 at 10:47
  • $\begingroup$ @HAHelfgott I don't know if it is standard. $\endgroup$ – Brendan McKay Oct 15 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.