patternModerate
Does a graph always have a minimum spanning tree that is binary?
Viewed 0 times
graphalwaysminimumthatbinarydoesspanninghavetree
Problem
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?
Solution
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.
In fact, the general problem of finding a degree-constrained minimum spanning tree is NP-complete.
Context
StackExchange Computer Science Q#32112, answer score: 18
Revisions (0)
No revisions yet.