Question 59

The graph $G = (V, E)$ has vertices $V = \{v_1, v_2, \dots, v_{100}\}$ and edge weights $w(v_i, v_j) = |i - j|$ for all $1 \le i < j \le 100$.

Minimum edge weight analysis:

• Since $i \ne j$ and indices are integers, the minimum possible weight for any edge in $G$ is:
  $$\min |i - j| = 1$$
• Edges of weight 1 are exactly the adjacent-index pairs: $(v_i, v_{i+1})$ for $i = 1, 2, \dots, 99$.

Spanning tree construction:

• Consider the subgraph formed by the 99 edges: $E_{\text{path}} = \{(v_1, v_2), (v_2, v_3), \dots, (v_{99}, v_{100})\}$.
• This forms a simple path spanning all 100 vertices of $V$ without any cycles.
• A spanning tree on 100 vertices must contain exactly $100 - 1 = 99$ edges.
• Since every edge in $E_{\text{path}}$ has the absolute minimum weight possible in $G$ (weight 1), no spanning tree can have a smaller total weight.
• Total weight of the minimum spanning tree:
  $$\text{Weight} = \sum_{i=1}^{99} w(v_i, v_{i+1}) = 99 \times 1 = 99$$