835 views

Consider a weighted undirected graph with vertex set $V = \{ n1, n2, n3, n4, n5, n6 \}$ and edge set $E = \{(n1,n2,2), (n1,n3,8), (n1,n6,3), (n2,n4,4), (n2,n5,12), (n3,n4,7), (n4,n5,9), (n4,n6,4)\}$. The third value in each tuple represents the weight of the edge specified in the tuple.

1. List the edges of a minimum spanning tree of the graph.
2. How many distinct minimum spanning trees does this graph have?
3. Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?
4. Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning tree of a graph?
edited | 835 views

a) edges with weight: $\text{2,3,4,7,9}$

b) no of distinct minimum spanning tree: $2$ (2nd with the different edge of weight $4$)

c) yes

d) yes

Edit:- Combining both answers into $1$.

edited
+1
Although question is simple but it will be good if you can add some explanation for other options for justification.

Minimum spanning tree:

0

1
2
–1 vote
3
4
5
6