I have a graph and I need to find a minimum spanning tree to a given graph. What is to be done so that the output obtained is a binary tree?

  • $\begingroup$ I just need to know if it is possible or not. I have done some digging though. I just want to know if there is any way to generate a spanning tree which is binary as well. $\endgroup$
    – Aditya.M
    Oct 20, 2014 at 7:08

1 Answer 1


There is nothing to be done: for instance, let $S_k$ denote the star graph with $k$ leaves. The graph $S_k$ has a unique spanning tree (which is $S_k$ itself), and it has a vertex with degree exactly $k$.

In fact, the general problem of finding a degree-constrained minimum spanning tree is NP-complete.


Your Answer

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

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