2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Interesting question! What are your thoughts on it? $\endgroup$ Oct 26, 2022 at 12:07
  • $\begingroup$ I tried several examples, and believe this conclusion is correct. P.S. If you think this is an interesting question, please give it a star such that more people can help to solve it :) @MatthewLeingang $\endgroup$ Oct 26, 2022 at 13:06
  • 1
    $\begingroup$ @MishaLavrov The question in the body is what I want to ask. Sorry about the misleading in the title. I have modified the title. Besides, what I want is that the spanning tree has as much as $O(n_{\geq 3})$ nodes with degree at least $3$. $\endgroup$ Oct 27, 2022 at 5:54
  • 1
    $\begingroup$ You want to write $\Omega(n_{\ge 3})$ or $\Theta(n_{\ge 3})$ in that case: $O(n_{\ge 3})$ is specifically an uppr bound. $\endgroup$ Oct 27, 2022 at 13:48

1 Answer 1

1
$\begingroup$

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:

  1. Vertices of degree exactly $3$.
  2. Vertices of degree $4$ or more with at least $3$ incident bridges. (That is, edges whose removal disconnects the graph.)
  3. 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)$.

$\endgroup$
4
  • $\begingroup$ I believe here is a typo: '... and every type-1 vertex has at most 3 adjacent type-2 vertices, so there are at most 1.5 times ...' It should be 'every type-1 vertex has at most 3 adjacent type-3 vertices', right? $\endgroup$ Oct 28, 2022 at 2:32
  • $\begingroup$ Yes, thank you for the correction. (Well, both of those are true, but "at most 3 adjacent type-3 vertices" is the relevant claim.) $\endgroup$ Oct 28, 2022 at 2:33
  • $\begingroup$ I notice in the counter-example, $\Omega(n_{\geq 3})=\Omega(\Delta)$. So, I have another interesting conjecture: for a connected undirected graph $G$, as long as $\Omega(n_{\geq 3})>\Omega(\Delta)$, $G$ has a spanning tree that has $\Omega(n_{\geq 3})$ branch nodes. It is a stronger version of your theorem. Intuitively, this conjecture may be true because $n_{\geq 3}-\Delta$ still has a rank of $\Omega(n_{\geq 3})$. Any idea/counter-example about this conjecture? $\endgroup$ Oct 28, 2022 at 12:22
  • 1
    $\begingroup$ I've added a generalization of my counter-example that avoids this. (Also, $\Omega_{n\ge 3} = \Omega(\Delta)$ doesn't quite make sense to write; you mean probably just $\Delta = \Omega(n_{\ge 3})$.) $\endgroup$ Oct 28, 2022 at 13:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .