Spanning Tree that Preserves the Number of Branch Vertices 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}$.
My question is: Is there always a spanning tree $T$ of $G$, such that the number of branch vertices in $T$ is still $\Theta(n_{\ge 3})$?
Here, $\Theta$ is the Big-Theta 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 and the degree preserving spanning tree. However, neither of which provide an answer to my question.
 A: A counterexample is the complete bipartite graph $K_{3,n}$.
Here, there are $3$ vertices of degree $n$, and $n$ vertices of degree $3$. However, in any spanning tree, at most one of the degree-$3$ vertices of the graph can be a branch vertex, or else a cycle is created. Therefore there is no spanning tree with more than $4$ branch vertices (three from the side with degree $n$, and one from the side with degree $3$).
We can generalize this example to one where $n_{\ge 3}$ and the maximum degree are not as close together. Take $k$ copies of $K_{3,n}$, and let $\{u_i, v_i, w_i\}$ be the degree-$n$ vertices of the $i^{\text{th}}$ copy. By adding edges $w_i u_{i+1}$ for $i=1, \dots, k-1$, we obtain a connected graph with maximum degree $n+1$ and with $n_{\ge 3} = k(n+3)$.
In any spanning tree, there are at most $4k$ branch vertices: from any copy of $K_{3,n}$, we can choose $u_i$, $v_i$, $w_i$, and at most one other vertex, or else we create a cycle. This is only a $\frac{4}{n+3}$ fraction of $n_{\ge 3}$.

Here is an interesting partial result.
Theorem. Every graph with $n_{\ge 3}$ vertices of degree at least $3$ and maximum degree $\Delta$ has a spanning tree with $\Omega(n_{\ge 3}/\Delta)$ branch vertices.
(Note that this is asymptotically matched by the second example above.)
Proof. Begin by iteratively deleting any edges for which this will keep the graph connected and keep the same value of $n_{\ge 3}$. After we've done this, the vertices of degree $3$ or more can be classified into $3$ types:

*

*Vertices of degree exactly $3$.

*Vertices of degree $4$ or more with at least $3$ incident bridges. (That is, edges whose removal disconnects the graph.)

*Vertices of degree $4$ or more with at least $2$ adjacent vertices of degree exactly $3$.

(Every vertex of degree $4$ or more must be type 2 or type 3, or else it has at most $2$ incident bridges and at most $1$ edge to a vertex of degree exactly $3$, so at least one remaining edge out of the vertex could still be removed.)
Every type-3 vertex has at least $2$ adjacent type-1 vertices, and every type-1 vertex has at most $3$ adjacent type-3 vertices, so there are at most $1.5$ times as many type-3 vertices as type-1. So if we forget about type-3 vertices and only look at types 1 and 2, we still have at least $\frac25 n_{\ge 3}$ vertices to look at.
Among the type 1 vertices, greedily pick a subset $S$ such that no two vertices of $S$ are at distance $1$ or $2$. This constraint eliminates fewer than $3\Delta$ other possibilities every time we pick one, so at least a $\frac1{3\Delta}$ fraction of the type-1 vertices make it into $S$.
Now pick a spanning tree as follows: for every vertex in $S$, pick all its edges (which cannot yet create a cycle) and then complete the resulting forest to an arbitrary spanning tree. In the result, every vertex of $S$ is a branch vertex, and so is every type-2 vertex (because those must keep all their bridges). As a result, we get at least $\frac1{3\Delta} \cdot \frac25 n_{\ge 3}$ branch vertices, which is $\Omega(n_{\ge 3}/\Delta)$.
