What is the number that a minimum spanning tree can have a vertex with degree at most? Is there any rule? Is it related to the number of vertex or edge? Or not?

  • $\begingroup$ A minimum spanning tree could be a star, and so have a vertex of degree $n-1$, where $n$ is the number of vertices. $\endgroup$ – Yuval Filmus Feb 14 '18 at 12:26
  • $\begingroup$ Ok, then at most n-1 $\endgroup$ – LSG Feb 14 '18 at 12:31
  • $\begingroup$ @LSG Yes but that applies to any vertex of any $n$-vertex graph. $\endgroup$ – David Richerby Feb 14 '18 at 13:48

Suppose that the graph is already a tree. Then the minimum spanning tree is the graph itself. In particular, if we take a star on $n$ vertices, we obtain a minimum spanning tree having a vertex of degree $n-1$. This is optimal, since in a graph containing $n$ vertices, all degrees are at most $n-1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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