Consider a graph $G = (V, E)$, where $ V = \{ v_1,v_2,…,v_{100} \}$, \(E = \{ (v_i, v_j) ∣ 1≤ i

Question

Consider a graph $G = (V, E)$, where $ V = \{ v_1,v_2,…,v_{100} \}$, $E = \{ (v_i, v_j) ∣ 1≤ i < j ≤ 100 \}$ and weight of the edge $(v_i, v_j)$ is $ ∣i–j∣$. The weight of minimum spanning tree of $G$ is ________.

Accepted Answer

Correct answer: 99 — Answer: 99 Key idea: the smallest possible edge weight is 1 (between consecutive indices), and we can use 99 such edges to span all 100 vertices. There are exactly 99 edges of weight 1: (v1,v2),(v2,v3),…,(v99,v100). These edges form a path that connects every vertex, so they give a spanning tree of total weight 99. Any spanning tree on 100 vertices has 99 edges, and every edge weight in the graph is at least 1 (since |i−j| ≥ 1 for i ≠ j). Thus the total weight of any spanning tree is at least 99. Because 99 is achievable and is a lower bound, the weight of the minimum spanning tree is 99.

Consider a graph \(G = (V, E)\), where \( V = \{ v_1,v_2,…,v_{100} \}\), \(E =…