GATE 2016 CS (CS1) – Question 49
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 ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 7
Explanation
A spanning tree of $K_4$ has 3 edges. We want the largest possible weight of the **minimum** spanning tree.
To make the MST heavy, make the cheap edges useless: put the three lightest edges (weights 1, 2, 3) on a triangle. A tree cannot contain a cycle, so Kruskal takes weights 1 and 2, rejects 3 (it would close the triangle), and must take the next cheapest edge that reaches the fourth vertex, which has weight 4.
$$\text{MST weight}=1+2+4=\mathbf{7}.$$
Any other arrangement gives a lighter MST (for example, if 1, 2, 4 formed the triangle, then the MST is $1+2+3=6$).
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2016 CS (CS1) Q50
- GATE 2017 CS (CS1) Q36
- GATE 2014 CS (CS1) Q13
- GATE 2014 CS (CS1) Q21
- GATE 2014 CS (CS1) Q23
- GATE 2014 CS (CS2) Q24
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →