There are 5 cities in a network. The cost of building a road directly between…

A Minimum Spanning Tree (MST) of a connected weighted graph is a subset of edges that connects every vertex using the minimum possible total edge weight, contains no cycles, and uses exactly (number of vertices − 1) edges. Kruskal's algorithm builds an MST greedily: sort all edges by weight and repeatedly add the smallest remaining edge, skipping any edge that would create a cycle, until every vertex is connected.

For the 5 cities, list every usable edge (finite entries only) with its weight and sort by increasing cost:

1. (1-2) = 3

2. (2-3) = 3

3. (1-3) = 5

4. (4-5) = 7

5. (2-5) = 8

6. (2-4) = 9

7. (1-5) = 9

8. (3-5) = 10

9. (1-4) = 11

The edge (3-4) is not usable, since C(3, 4) = ∞.

Apply Kruskal's rule, adding an edge only if it does not close a cycle:

1. Add (1-2) = 3 — connects {1, 2}.

2. Add (2-3) = 3 — connects {1, 2, 3}.

3. Skip (1-3) = 5 — both endpoints are already in {1, 2, 3}, so adding it would form a cycle.

4. Add (4-5) = 7 — connects {4, 5}.

5. Add (2-5) = 8 — the smallest remaining edge that joins the two separate groups {1, 2, 3} and {4, 5}.

6. Stop — 4 edges have now been added for 5 vertices, so every city is in one connected component.

Total MST cost = 3 + 3 + 7 + 8 = 21.

Cross-check: the tree uses exactly 5 − 1 = 4 edges and every city — 1, 2, 3, 4, 5 — appears in the final connected set, confirming it is a valid spanning tree. No cheaper alternative exists: the only other edges crossing between {1, 2, 3} and {4, 5} at this stage were (1-5) = 9 and (3-5) = 10, both costlier than the chosen (2-5) = 8, and every unchosen edge inside a single group only closes a cycle, so 21 cannot be improved.

Therefore, the least cost of making all cities reachable from each other is 21.