Question 9801 – Minimum-Spanning-Tree

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. 

(a) List the edges of a minimum spanning tree of the graph.
(b) How many distinct minimum spanning trees does this graph have?
(c) Is the minimum among the edge weights of a minimum spanning tree unique overall possible minimum spanning trees of a graph?
(d) Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?

Correct Answer: A