4 A simplified map of an area of moorland is shown below. The vertices represent farmhouses and the arcs represent the paths between the farmhouses. The weights on the arcs show distances in km.
\includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-4_618_1420_356_319} Ted wants to visit each farmhouse and then return to his starting point.

1. In your answer book the arcs have been sorted into increasing order of weight. Use Kruskal’s algorithm to find a minimum spanning tree for the network, and give its total weight. Hence find a route visiting each farmhouse, and returning to the starting point, which has length 82 km .
2. Give the weight of the minimum spanning tree for the six vertices \(A , B , C , E , F , G\). Hence find a route visiting each of the seven farmhouses once, and returning to the starting point, which has length 81 km .
3. Show that the nearest neighbour method fails to produce a cycle through every vertex when started from \(A\) but that it succeeds when started from \(B\). Adapt this cycle to find a complete cycle of total weight less than 70 , and find the total length of the shorter cycle.