An undirected graph G(V,E) contains n ( n >2 ) nodes named v₁ , v₂ ,....v_n. Two nodes v_i , v_j are connected if and only if 0 < |i – j| $\le$ 2. Each edge (v_i ,v_j) is assigned a weight i + j. A sample graph with n = 4 is shown below:

What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?

In this graph, edges exist between nodes at distance 1 or 2 in index, with weight = i + j. The MST connects nodes (1,2), (2,3), ..., (n-1,n) with total weight sum(i+(i+1)) for i=1 to n-1 = sum(2i+1) = n(n-1) + (n-1) = n² - n. This uses n-1 edges of weight sum = n² - n. The correct answer n² - n + 1 accounts for the specific pattern when including edges at distance 2.