Graph Algorithms

Statement for Linked Answer Questions 54 and 55: An undirected graph $G(V, E)$ contains $n$ ($n > 2$) nodes named $v_1, v_2, \ldots, 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?

Statement for Linked Answer Questions 54 and 55: An undirected graph $G(V, E)$ contains $n$ ($n > 2$) nodes named $v_1, v_2, \ldots, 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. The length of the path from $v_5$ to $v_6$ in the MST of previous question (Q.54) with $n = 10$ is