Starting at A , use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for \(G\).

By first deleting vertex A , use the deleted vertex algorithm together with Kruskal’s algorithm to find a lower bound for the travelling salesman problem for \(G\).

the edges are traversed in the following order

AB     A1

BC

CF     A1

FE

ED     A1

DA   A1

\({\text{upper bound}} = {\text{weight of this cycle}} = 4 + 1 + 2 + 7 + 11 + 8 = 33\)     A1

[5 marks]

having deleted A, the order in which the edges are added is

BC     A1

CF     A1

CD     A1

EF     A1

Note:     Accept indication of the correct order on a diagram.

to find the lower bound, we now reconnect A using the two edges with the lowest weights, that is AB and AF     (M1)(A1)

\({\text{lower bound}} = 1 + 2 + 5 + 7 + 4 + 6 = 25\)     A1

Note:     Award (M1)(A1)A1 for \({\text{LB}} = 15 + 4 + 6 = 25\) obtained either from an incorrect order of correct edges or where order is not indicated.

[7 marks]