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

MathOverflow Asked by H A Helfgott on January 31, 2021

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

## Related Questions

### Duality of finite signed measures and bounded continuous functions

3  Asked on February 2, 2021

### Toposes with only preorders of points

1  Asked on February 1, 2021 by matthias-hutzler

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

1  Asked on January 31, 2021 by h-a-helfgott

### The level sets of a differentiable function is a manifold

1  Asked on January 31, 2021 by user8948

### Kruskal-Katona type question for union-closed families of sets

0  Asked on January 30, 2021 by peter-hegarty

### First Chern class and field extensions

1  Asked on January 28, 2021 by manifold

### Distributive lattices with periodic Coxeter matrix

0  Asked on January 27, 2021

### What does go wrong in Cellular homology if one considers projective limits of celullar complexes instead of CW-complexes?

0  Asked on January 27, 2021 by lo-brunswic

### On $sum_{k=1}^nk^3 = x^3 + y^3$ with $x,y ge 1$

0  Asked on January 26, 2021 by alkan

### Is a set over which dynamics are topologically conjugate to a shift map on two symbols always repelling?

0  Asked on January 26, 2021 by aghostinthefigures

### Large deviation for Brownian occupation time

1  Asked on January 26, 2021 by lye012

### How to turn a shuffled deck of card into bits

1  Asked on January 24, 2021 by zachary-vance

### Sparse signal recovery (nonlinear case)

0  Asked on January 24, 2021 by sbastien-loisel

### High direct image of dualizing sheaf

0  Asked on January 24, 2021 by xin-fu

### How badly can the GCH fail globally?

1  Asked on January 24, 2021 by sam-roberts

### Torque term coming from added mass effects

2  Asked on January 24, 2021 by user114331

### Nonseparable Hilbert spaces

6  Asked on January 23, 2021 by truebaran

### Connectedness of the set having a fixed distance from a closed set 2

1  Asked on January 23, 2021 by m-rahmat

### Filtered colim of F-groups

1  Asked on January 21, 2021 by ofra

### Expectation of random matrix (minimum positive eigenvalue)

0  Asked on January 20, 2021 by ripon