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}$. 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 and the degree preserving spanning tree. However, neither of which provide an answer to my question.

$\endgroup$

1 Answer 1

2
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.