GATE 2020 CS – Question 59
Consider a graph $G=(V,E)$, where $V=\{v_1,v_2,\dots,v_{100}\}$, $E=\{(v_i,v_j)\mid 1\le i<j\le 100\}$, and weight of the edge $(v_i,v_j)$ is $|i-j|$. The weight of minimum spanning tree of $G$ is ______.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 99 to 99
Explanation
The path $v_1-v_2-\dots-v_{100}$ uses the 99 lightest edges, each of weight 1. Total weight 99.