An undirected graph $G(V,E)$ contains $n \: (n>2)$ nodes named $v_1,v_2, \dots, v_n$. Two nodes $v_i, v_j$ are connected if and only if $ 0 < \mid i-j\mid \leq 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?
- $\frac{1}{12} (11n^2 - 5 n)$
- $n^2-n+1$
- $6n-11$
- $2n+1$