# Does a graph always have a minimum spanning tree that is binary?

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?

• 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. – Aditya.M Oct 20 '14 at 7:08

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$.