Let G be a complete undirected graph on 4 vertices, having 6 edges with…
2016
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is _________.
Attempted by 176 students.
Show answer & explanation
Correct answer: 7
Key idea: Kruskal's algorithm takes edges in increasing order, so the smallest and second smallest edges are always included in the MST for this graph.
Label the sorted weights as e1 = 1, e2 = 2, e3 = 3, e4 = 4, e5 = 5, e6 = 6.
Kruskal will take e1 and e2 (they cannot form a cycle after selecting at most one edge). The third edge chosen is either e3 (if it does not create a cycle) or, if e1, e2, e3 form a triangle, Kruskal skips e3 and takes e4 instead.
Thus the MST weight is either 1 + 2 + 3 = 6 or 1 + 2 + 4 = 7, so the maximum possible MST weight is 7.
Example construction: place weights 1, 2, 3 on the three edges of a triangle among three vertices and put weight 4 on an edge connecting the fourth vertex to that triangle. Kruskal then picks edges with weights 1, 2, and 4, giving an MST of total weight 7.
A video solution is available for this question — log in and enroll to watch it.