GATE CS 2011 Q55 — Minimum Spanning Trees

To find the length of the path from $v_5$ to $v_6$ in the Minimum Spanning Tree (MST) of the graph with $n = 10$, we first construct the MST using Kruskal's algorithm.

The edges of the graph can be categorized into two types:

1. Edges of the form $(v_i, v_{i+1})$ with weight $2i + 1$
2. Edges of the form $(v_i, v_{i+2})$ with weight $2i + 2$

Sorting all edges by weight and applying Kruskal's algorithm (avoiding cycles) yields the following edges in the MST:

• $(v_1, v_2)$ with weight $3$
• $(v_1, v_3)$ with weight $4$
• $(v_2, v_4)$ with weight $6$
• $(v_3, v_5)$ with weight $8$
• $(v_4, v_6)$ with weight $10$
• $(v_5, v_7)$ with weight $12$
• $(v_6, v_8)$ with weight $14$
• $(v_7, v_9)$ with weight $16$
• $(v_8, v_{10})$ with weight $18$

Since the MST is a tree, there is a unique path between any two nodes. The path from $v_5$ to $v_6$ in this MST is:

$$\text{Path: } v_5 \xrightarrow{8} v_3 \xrightarrow{4} v_1 \xrightarrow{3} v_2 \xrightarrow{6} v_4 \xrightarrow{10} v_6$$

Summing the weights of the edges along this path:

$$\text{Length} = 8 + 4 + 3 + 6 + 10 = 31$$