Consider the undirected graph below: Using Prim’s algorithm to construct a…

Answer: (a,b), (a,h), (g,h), (f,g), (c,f), (c,i), (c,d), (d,e)

Reasoning (step-by-step using Prim’s algorithm starting from node a):

1. Step 1: Start at a. Available edges from a are (a,b)=4 and (a,h)=8. Choose (a,b) because it has the smaller weight (4).

2. Step 2: Tree = {a,b}. Crossing edges are (a,h)=8, (b,c)=8 and (b,h)=11. The smallest crossing edges have weight 8; choosing (a,h) (as in the given sequence) is a valid tie-break, so add (a,h).

3. Step 3: Tree = {a,b,h}. The smallest crossing edge is (g,h)=1, so add (g,h).

4. Step 4: Tree now includes g. The smallest crossing edge is (f,g)=2, so add (f,g).

5. Step 5: With f added, the cheapest way to bring c into the tree is (c,f)=4 (other crossing edges are heavier), so add (c,f).

6. Step 6: Now that c is in the tree, (c,i)=2 is the smallest crossing edge incident on the tree, so add (c,i).

7. Step 7: Next the smallest remaining crossing edge to connect new vertices is (c,d)=7, so add (c,d).

8. Step 8: The only remaining vertex (e) is connected via (d,e)=9, so add (d,e). The tree is now a minimum spanning tree.

Why the other sequences are rejected (concise):

• The sequence that picks (b,h) as the second edge is invalid because after (a,b) there exists a lighter crossing edge of weight 8 ((a,h) or (b,c)), so selecting the heavier (b,h) (weight 11) violates Prim’s greedy choice.

• Any sequence that tries to add an edge connecting two vertices that are both outside the current tree (for example adding (g,h) when neither g nor h is yet in the tree) is impossible under Prim, because each chosen edge must connect the current tree to a new vertex.

• Ties between equal-weight crossing edges can lead to different valid orders; the given accepted sequence assumes a particular tie-breaking. The chosen answer is consistent with breaking the tie in favor of (a,h) at the second step and thereafter always picking the minimum crossing edge.