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

Question

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| ≤ 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?

(A) 1/12 (11n² - 5n)

(B) n² - n + 1

(C) 6n - 11

(D) 2n + 1

Answer 1

Correct option is (B) n² - n + 1