The GATE Grind

GATE 2016 CS (CS1) – Question 49

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Numerical answer

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

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →