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.
The length of the path from $v_5$ to $v_6$ in the MST of previous question with $n=10$ is
Above is the graph....
Below is the MST.
Length of the path from v5 to v6= 8+4+3+6+10= 31 (Ans)
There is no direct edge between Vi and Vi+1 vertex in mst except V1 to V2 so path from Vi and Vi+1 includes all edges from v1 to Vi+1 which are in mst:
edge weights in mst:
=3 + 4 + 6 + 8 + 10 + 12 +...+*(2(n-1))
=1+(2+ 4+6+....till n-1 terms)
In this case v6 = 62-6+1 =31
Answer is C.
It can be easily obtained by drawing graph for up to 7 vertices.
NO need to draw full spanning tree..
there is no direct edge between Vi and Vi+1 vertex so path from Vi and Vi+1 includes all edges from v1 to Vi+1 which are in mst:
equation: n2-n + 1 from previous question
in our case v6 = 62-6+1 =31
X->YZ , Y->XZ , ...