1.1k 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 | 1.1k views

(A) Edges with weights: $\text{2,3,4,7,9}$

(B) Number of distinct minimum spanning tree: $2$ (2nd with a different edge of weight $4$)

(C) yes

(D) yes

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