TransWikia.com

Spanning trees: the last darn $1/4$

MathOverflow Asked by H A Helfgott on January 31, 2021

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

One Answer

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.

Answered by Brendan McKay on January 31, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP