HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

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

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#32112, answer score: 18

Revisions (0)

No revisions yet.