- This question should be answered on the sheet provided.
The table below shows the distances in miles between five villages. Jane lives in village \(A\) and is about to take her daughter's friends home to villages \(B , C , D\) and \(E\). She will begin and end her journey at \(A\) and wishes to travel the minimum distance possible.
| \(A\) | \(B\) | \(C\) | \(D\) | \(E\) |
| \(A\) | - | 4 | 7 | 8 | 2 |
| \(B\) | 4 | - | 1 | 5 | 6 |
| \(C\) | 7 | 1 | - | 2 | 7 |
| \(D\) | 8 | 5 | 2 | - | 3 |
| \(E\) | 2 | 6 | 7 | 3 | - |
- Obtain a minimum spanning tree for the network and hence find an upper bound for the length of Jane's journey.
- Using a shortcut, improve this upper bound to find an upper bound of less than 15 miles.
(2 marks)