Please could I ask for some help with this exam past paper question:
A connected graph G has five vertices and has eight edges with lengths 8, 10, 10,
11, 13, 17, 17 and 18.
(a) Find the minimum length of a minimum spanning tree for G. (2 marks)
(b) Find the maximum length of a minimum spanning tree for G. (2 marks)
(c) Draw a sketch to show a possible graph G when the length of the minimum spanning tree is 53. (3 marks)
ANSWER:-
6(a) Min MST = 8 + 10 +10 + 11 = 39
(b) Max MST = 8 + 17 +17 +18 = 60 Alternatively: 8 + 18 + 2 others = 60
I found this question discussed here and some people think there is an error in the question.
I'm not sure, the answer to (a) seems reasonable. For (b) the answer states the solution must include 8. I found this entry on wikipedia :
If the edge of a graph with the minimum cost e is unique, then this edge is included in any MST.
Proof: if e was not included in the MST, removing any of the (larger cost) edges in the cycle formed after adding e to the MST, would yield a spanning tree of smaller weight.
In this example 8 is the minimum cost edge, so I based on this result in must be in any MST.
Does anyone know if this is a well-known result (perhaps with a name?) it is supplied without a reference on wikipedia. Thanks, C