MST with variable edge weight

3 [Figure 1, printed on the insert, is provided for use in part (b) of this question.]
The diagram shows a network of roads. The number on each edge is the length, in kilometres, of the road. \includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-03_716_1303_559_388}

1. 1. Use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the network.
   2. State the length of your minimum spanning tree.
2. 1. Use Dijkstra's algorithm on Figure 1 to find the shortest distance from \(A\) to \(J\).
   2. A new road, of length \(x \mathrm {~km}\), is built connecting \(I\) to \(J\). The minimum distance from \(A\) to \(J\) is reduced by using this new road. Find, and solve, an inequality for \(x\).

3 The network below shows vertices \(A , B , C , D\) and \(E\). The number on each edge shows the distance between vertices. \includegraphics[max width=\textwidth, alt={}, center]{fb95068f-f76d-492a-b385-bce17b26ae30-06_563_736_402_651}

1. 1. In the case where \(x = 8\), use Kruskal's algorithm to find a minimum spanning tree for the network. Write down the order in which you add edges to your minimum spanning tree.
   2. Draw your minimum spanning tree.
   3. Write down the length of your minimum spanning tree.
2. Alice draws the same network but changes the value of \(x\). She correctly uses Kruskal's algorithm and edge \(C D\) is included in her minimum spanning tree.
   1. Explain why \(x\) cannot be equal to 7 .
   2. Write down an inequality for \(x\).

3. \begin{figure}[h] \end{figure} [The weight of the network is \(5 x + 246\) ]

1. Explain why it is not possible to draw a graph with an odd number of vertices of odd valency. Figure 2 represents a network of 14 roads in a town. The expression on each arc gives the time, in minutes, to travel along the corresponding road. Prim's algorithm, starting at A, is applied to the network. The order in which the arcs are selected is \(\mathrm { AD } , \mathrm { DH } , \mathrm { DG } , \mathrm { FG } , \mathrm { EF } , \mathrm { CG } , \mathrm { BD }\). It is given that the order in which the arcs are selected is unique.
2. Using this information, find the smallest possible range of values for \(x\), showing your working clearly. A route that minimises the total time taken to traverse each road at least once is required. The route must start and finish at the same vertex. Given that the time taken to traverse this route is 318 minutes,
3. use an appropriate algorithm to determine the value of \(x\), showing your working clearly.