<p>No, not even close.</p>
<p><strong>Lemma 1.</strong> <em>For any <span class="math-container">$n\ge 6$</span>, all <span class="math-container">$n$</span> vertices in the complete bipartite graph <span class="math-container">$K_{3,n-3}$</span> are branch vertices, but each spanning tree of the graph has at most 4 branch vertices.</em></p>
<p><em>Proof.</em>  The spanning tree cannot have two branch vertices from the right side (of size <span class="math-container">$n-3$</span>) because they would each have to have all 3 edges to the left side, creating a cycle. <span class="math-container">$~~~\Box$</span></p>
<p>What's more, each spanning tree has at most 5 vertices of degree more than 1!</p>

CC BY-SA 4.0
2022-10-27T17:31:14.080Z
2022-10-27T18:54:23.517Z
2022-10-27T18:54:23.517Z
Neal Young
<p>Suppose a undirected connected graph <span class="math-container">$G$</span>, denote the number of vertices in <span class="math-container">$G$</span> as <span class="math-container">$n$</span>, number of branch vertices (i.e., vertices with degree <span class="math-container">$\geq 3$</span>) as <span class="math-container">$n_{\geq 3}$</span>. Suppose <span class="math-container">$n_{\geq 3}&gt;\log(n)$</span>.</p>
<p>My question is: Is there always a spanning tree <span class="math-container">$T$</span> of <span class="math-container">$G$</span>, such that the number of branch vertices in <span class="math-container">$T$</span> is still as much as <span class="math-container">$O(n_{\geq 3})$</span>?</p>
<p>Here, <span class="math-container">$O$</span> is the Big-O notation in computational complexity.</p>
<p>I tried several examples and think this conjecture is correct.</p>
<p>This question is related to the <a href="https://arxiv.org/abs/1709.04937" rel="nofollow noreferrer">minimum branch vertices spanning tree</a> and the <a href="https://pdf.sciencedirectassets.com/271536/1-s2.0-S0012365X00X00787/1-s2.0-S0012365X00000054/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjECYaCXVzLWVhc3QtMSJIMEYCIQD1EynsIjAFYZwRQVsAipHRQw1LAPlofPFlwQ50OZyw5wIhAJsiSj5sVuy1O0l9KI8%2FLjRVux1CRmMhLQyZRarqHvK%2BKtUECP%2F%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEQBRoMMDU5MDAzNTQ2ODY1Igxf0ebdVinv%2BwHEDt0qqQQud6FwyHecbRz%2FS9U%2FKhNePSwpjc%2FUDlkj906pHVmidB1OE6IhNOF2sT2Ft6XuPlAtF0j6j850SPTnjLEN1kqqqvBxvK0XmaXZ3cRlOkO9UD97rn3Lt55uPlDhTS8uwmvZVzC%2Bn9yJLLUY%2F%2FzkrZdSglJwpwIFcXpmeU8QAAykaJGxGM3%2Ffh8mwQEEkwnDSGJTSFNP8STMjVhu8cH%2F8l2LZaTESdVzTIGv%2Fz5lFJVqNJWKOGwcVMFqkXuPBo6SdyBfa4UfaqvG3G9ELHdylaHb0tKrABn9NxiyaMOOFOOSgLHXsK2qCsYhTOgzXQ2rm3CF57UzJaKfW2A8dIMwLUUsj3LZR3YtgMnn42BkUjZ4nYISumpDO1EbW8dJtWW%2BzLCHQddkCKX5u4FFj5wBoQp2BQqyMg08mQWuATwtHb6ZoQ7YV%2BgUGxDwLqknvCURapxqDcUdQ33LSyHxUvCoGs%2Bt5U6sHmWD8ftOgpvR%2FDu5FIfyFzkWFsayEwX1jkQkW4z%2BHm2NRi%2BB%2FqKIDgYSpiDwCl9CdsEMHP0aiX99x8QP6YTrRZbT4%2B1YTT7CBJBsr8fWDcVOtyPQvWk0%2Fi1IENLSk41qDf5nOB%2BQYwvDyfsArOfq32UkrMGOV5cUmSGkBy7rh4bphwEZfd8F0hvMaPvhqDJoRQHPMGvzkOGethBWAGzul%2BHch1ONyOqXC1EpfBcyVmyq%2FP%2BgfF0GSXREOMi%2BQIwyeJcOFOisMOu66JoGOqgBciGQFhFfYmYKA9bdOBywG6ykKPJjRiwIWhjy1q0NNOW29Fmg1GB7O%2FQzPKhvwsJxZHVIiXL7ryC3CvwEIoLC7gmTyVbh2tRzBvayaYxAggXxXK7pVltokUMMGXMsZXTg8n1KsAtoVEWoACc3wdXvGjE37dtB10AYFrtNv2%2F6GXZt0RLh0iXv28yoTnA7Z3GHuacpO2b542yP7WEFSY3kb5XVHHrKms0w&amp;X-Amz-Algorithm=AWS4-HMAC-SHA256&amp;X-Amz-Date=20221027T070919Z&amp;X-Amz-SignedHeaders=host&amp;X-Amz-Expires=300&amp;X-Amz-Credential=ASIAQ3PHCVTYTER23AQL%2F20221027%2Fus-east-1%2Fs3%2Faws4_request&amp;X-Amz-Signature=7cf4ddeb23580a45b15d19173936f6395b885b8e66afbe1999e5ac8c23e85236&amp;hash=84df11644ffc1dd7accdc1e2ef58bd515763051862419f1bed29231655530bb4&amp;host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&amp;pii=S0012365X00000054&amp;tid=spdf-7755acc4-9729-43a8-b412-7f6cea6cbb03&amp;sid=1b2986fb1cbbf642332a78b84fb07ef422cagxrqb&amp;type=client&amp;ua=51545e5f5603515d5a05&amp;rr=76099b038f190964" rel="nofollow noreferrer">degree preserving spanning tree</a>. However, neither of which provide an answer to my question.</p>

<graph-theory><tree><spanning-tree>
Spanning Tree that Preserves the Number of Branch Vertices
Mingzhou Liu
# Spanning Tree that Preserves the Number of Branch Vertices

(Asked by: username_0 on 2022-10-27)

Suppose a undirected connected graph $G$, denote the number of vertices in $G$ as $n$, number of branch vertices (i.e., vertices with degree $\geq 3$) as $n\_{\geq 3}$. Suppose $n\_{\geq 3}>\log(n)$.

My question is: Is there always a spanning tree $T$ of $G$, such that the number of branch vertices in $T$ is still as much as $O(n\_{\geq 3})$?

Here, $O$ is the Big-O notation in computational complexity.

I tried several examples and think this conjecture is correct.

This question is related to the [minimum branch vertices spanning tree](https://arxiv.org/abs/1709.04937) and the [degree preserving spanning tree](https://pdf.sciencedirectassets.com/271536/1-s2.0-S0012365X00X00787/1-s2.0-S0012365X00000054/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjECYaCXVzLWVhc3QtMSJIMEYCIQD1EynsIjAFYZwRQVsAipHRQw1LAPlofPFlwQ50OZyw5wIhAJsiSj5sVuy1O0l9KI8%2FLjRVux1CRmMhLQyZRarqHvK%2BKtUECP%2F%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEQBRoMMDU5MDAzNTQ2ODY1Igxf0ebdVinv%2BwHEDt0qqQQud6FwyHecbRz%2FS9U%2FKhNePSwpjc%2FUDlkj906pHVmidB1OE6IhNOF2sT2Ft6XuPlAtF0j6j850SPTnjLEN1kqqqvBxvK0XmaXZ3cRlOkO9UD97rn3Lt55uPlDhTS8uwmvZVzC%2Bn9yJLLUY%2F%2FzkrZdSglJwpwIFcXpmeU8QAAykaJGxGM3%2Ffh8mwQEEkwnDSGJTSFNP8STMjVhu8cH%2F8l2LZaTESdVzTIGv%2Fz5lFJVqNJWKOGwcVMFqkXuPBo6SdyBfa4UfaqvG3G9ELHdylaHb0tKrABn9NxiyaMOOFOOSgLHXsK2qCsYhTOgzXQ2rm3CF57UzJaKfW2A8dIMwLUUsj3LZR3YtgMnn42BkUjZ4nYISumpDO1EbW8dJtWW%2BzLCHQddkCKX5u4FFj5wBoQp2BQqyMg08mQWuATwtHb6ZoQ7YV%2BgUGxDwLqknvCURapxqDcUdQ33LSyHxUvCoGs%2Bt5U6sHmWD8ftOgpvR%2FDu5FIfyFzkWFsayEwX1jkQkW4z%2BHm2NRi%2BB%2FqKIDgYSpiDwCl9CdsEMHP0aiX99x8QP6YTrRZbT4%2B1YTT7CBJBsr8fWDcVOtyPQvWk0%2Fi1IENLSk41qDf5nOB%2BQYwvDyfsArOfq32UkrMGOV5cUmSGkBy7rh4bphwEZfd8F0hvMaPvhqDJoRQHPMGvzkOGethBWAGzul%2BHch1ONyOqXC1EpfBcyVmyq%2FP%2BgfF0GSXREOMi%2BQIwyeJcOFOisMOu66JoGOqgBciGQFhFfYmYKA9bdOBywG6ykKPJjRiwIWhjy1q0NNOW29Fmg1GB7O%2FQzPKhvwsJxZHVIiXL7ryC3CvwEIoLC7gmTyVbh2tRzBvayaYxAggXxXK7pVltokUMMGXMsZXTg8n1KsAtoVEWoACc3wdXvGjE37dtB10AYFrtNv2%2F6GXZt0RLh0iXv28yoTnA7Z3GHuacpO2b542yP7WEFSY3kb5XVHHrKms0w&X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Date=20221027T070919Z&X-Amz-SignedHeaders=host&X-Amz-Expires=300&X-Amz-Credential=ASIAQ3PHCVTYTER23AQL%2F20221027%2Fus-east-1%2Fs3%2Faws4_request&X-Amz-Signature=7cf4ddeb23580a45b15d19173936f6395b885b8e66afbe1999e5ac8c23e85236&hash=84df11644ffc1dd7accdc1e2ef58bd515763051862419f1bed29231655530bb4&host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&pii=S0012365X00000054&tid=spdf-7755acc4-9729-43a8-b412-7f6cea6cbb03&sid=1b2986fb1cbbf642332a78b84fb07ef422cagxrqb&type=client&ua=51545e5f5603515d5a05&rr=76099b038f190964). However, neither of which provide an answer to my question.

**Tags:** graph-theory, tree, spanning-tree

---

## 1 answers

### Answer by username_1 on 2022-10-27. Score: 2 | Accepted answer

No, not even close.

**Lemma 1.** *For any $n\ge 6$, all $n$ vertices in the complete bipartite graph $K\_{3,n-3}$ are branch vertices, but each spanning tree of the graph has at most 4 branch vertices.*

*Proof.* The spanning tree cannot have two branch vertices from the right side (of size $n-3$) because they would each have to have all 3 edges to the left side, creating a cycle. $~~~\Box$

What's more, each spanning tree has at most 5 vertices of degree more than 1!


---

