[Solved]: Does a graph always have a minimum spanning tree that is binary?

Problem Detail: 

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?

Asked By : Aditya.M

Answered By : Juho

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32112