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

1 AnswersConsider 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

3 Asked on February 2, 2021

duality fa functional analysis measure theory pr probability

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

1 Asked on January 31, 2021 by user8948

0 Asked on January 30, 2021 by peter-hegarty

1 Asked on January 28, 2021 by manifold

ag algebraic geometry complex manifolds dg differential geometry divisors

0 Asked on January 27, 2021

0 Asked on January 27, 2021 by lo-brunswic

0 Asked on January 26, 2021 by alkan

0 Asked on January 26, 2021 by aghostinthefigures

1 Asked on January 26, 2021 by lye012

1 Asked on January 24, 2021 by zachary-vance

0 Asked on January 24, 2021 by sbastien-loisel

combinatorial optimization compressed sensing convexity nonlinear optimization regularization

0 Asked on January 24, 2021 by xin-fu

1 Asked on January 24, 2021 by sam-roberts

2 Asked on January 24, 2021 by user114331

6 Asked on January 23, 2021 by truebaran

1 Asked on January 23, 2021 by m-rahmat

at algebraic topology gn general topology path connected real analysis

1 Asked on January 21, 2021 by ofra

ct category theory gr group theory homotopy theory limits and colimits

0 Asked on January 20, 2021 by ripon

eigenvalues expectation matrix analysis matrix theory random matrices

Get help from others!

Recent Questions

- MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- How do i draw a ray in unity
- How to test consistency of responses?
- How can I understand these variograms?

Recent Answers

- DMGregory on MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Philipp on How do i draw a ray in unity
- kjetil b halvorsen on How to test consistency of responses?
- Justin Markwell on Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- eric_kernfeld on How to test consistency of responses?

© 2022 AnswerBun.com. All rights reserved.