Consider a graph G = (V, E), where V = {v1, v2,..., v100}, E = {(vi, vj) | 1 ≤ i ≤ j ≤ 100}, and weight of the edge (vi, vj) is |i-j|. The weight of minimum spanning tree of G is ______.

Correct Answer:

99

Solution:

G = (V, E) where
V = {v1, v2,..., v100}
E = {(vi, vj) | 1 ≤ i ≤ j ≤ 100}

Weight of the edge (vi, vj) = |i-j|

Let's take some small examples and evaluate and see the pattern.

Example 1: Take 4 vertices and implement the given condition

MST for the above graph:

Minimum Weight of spanning tree of G = 3

Example 2: Take 5 vertices and implement the given condition

MST for the above graph:

Weight of minimum spanning tree = 4

So, similarly when we have 100 vertices then we will get 99 edges {(v1 → v2), (v2 → v3), (v3 → v4), (v4 → v5),...., (v99 → v100)} in MST of graph each having weight = 1

Weight of MST of given graph G = 99