4 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\). A programme of resurfacing some roads is undertaken to ensure that each village can access all other villages along a resurfaced road, while keeping the amount of road to be resurfaced to a minimum.
\includegraphics[max width=\textwidth, alt={}, center]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-08_1008_1043_589_497}

1. 1. Use Prim's algorithm starting from \(A\), showing the order in which you select the edges, to find a minimum spanning tree for the network.
   2. State the length of your minimum spanning tree.
   3. Draw your minimum spanning tree.
2. Given that Prim's algorithm is used with different start vertices, state the final edge to be added to the minimum spanning tree if:
   1. the start vertex is \(E\);
   2. the start vertex is \(G\).
3. Given that Kruskal's algorithm is used to find the minimum spanning tree, state which edge would be:
   1. the first to be included in the tree;
   2. the last to be included in the tree.