GATE 2016 CS – 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 uses 3 edges. The tree has the largest weight when the three lightest edges, 1, 2 and 3, form a triangle. A tree cannot contain a cycle, so it can use only two of them, namely 1 and 2. It must then add the next lightest edge that reaches the fourth vertex, which is 4. The weight is $1 + 2 + 4 = 7$.