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
Best Answer
Part $(b)$ is only true if we assume that $G$ has multiple edges but no loops.
The Wikipedia page is a little misleading; it might be more accurate to say that at least one of the lowest weight edges will be in a minimum spanning tree (in a loopless graph).
This is apparent from the application of Kruskal's Algorithm for constructing a minimum spanning tree. Essentially, select the lowest weight vertex at each step that will not introduce a cycle. Because it is impossible to create a cycle when selecting the first edge in a loopless graph (per assumption) Kruskal's Algorithm will always select it.
In order to rule out the length $10$,$10$, $11$, and $13$ edges, they must all create cycles if they are included with the $8$ edge; this implies that there is a multiple edge with $8$,$10$,$10$,$11$, and $13$ all connecting the same two vertices.
I would say it's very non-standard to allow multiple-edges but not loops in the graph, because problems are generally a matter of simple vs. non-simple, where loops are allowed in non-simple graphs. Clearly, you can obtain a higher result by making $8$,$10$,$10$, and $11$ edges all loops, while using the other $4$ to create the spanning tree.
I would ask your professor to clarify this point, and definitely ask during an exam if a question is vague.