(i)     Draw the graph \({\kappa _4}\) including the weights of all the edges.

(ii)     Use the nearest-neighbour algorithm, starting at vertex \({{\text{A}}_1}\), to find a Hamiltonian cycle.

(iii)     Hence, find an upper bound to the travelling salesman problem for this weighted graph.

Consider the graph \({\kappa _5}\). Use the deleted vertex algorithm, with \({{\text{A}}_5}\) as the deleted vertex, to find a lower bound to the travelling salesman problem for this weighted graph.

(i)     Use the nearest-neighbour algorithm, starting at vertex \({{\text{A}}_1}\), to find a Hamiltonian cycle.

(ii)    Hence find and simplify an expression in \(n\), for an upper bound to the travelling salesman problem for this weighted graph.

By splitting the weight of the edge \({{\text{A}}_i}{{\text{A}}_j}\) into two parts or otherwise, show that all Hamiltonian cycles of \({\kappa _n}\) have the same total weight, equal to the answer found in (c)(ii).

(i)          A1A1

Note: A1 for the graph, A1 for the weights.

(ii)     cycle is \({{\text{A}}_1}{{\text{A}}_2}{{\text{A}}_3}{{\text{A}}_4}{{\text{A}}_1}\)     A1

(iii)     upper bound is \(3 + 5 + 7 + 5 = 20\)     A1

[4 marks]

with \({{\text{A}}_5}\) deleted, (applying Kruskal’s Algorithm) the minimum spanning tree will consist of the edges \({{\text{A}}_1}{{\text{A}}_2},{\text{ }}{{\text{A}}_1}{{\text{A}}_3}{\text{, }}{{\text{A}}_1}{{\text{A}}_4}\), of weights 3, 4, 5     (M1)A1

the two edges of smallest weight from \({{\text{A}}_5}\) are \({{\text{A}}_5}{{\text{A}}_1}\) and \({{\text{A}}_5}{{\text{A}}_2}\) of weights 6 and 7     (M1)A1

so lower bound is \(3 + 4 + 5 + 6 + 7 = 25\)     A1

[5 marks]

(i)     starting at \({{\text{A}}_1}\) we go \({{\text{A}}_2},{\text{ }}{{\text{A}}_3}{\text{ }} \ldots {\text{ }}{{\text{A}}_n}\)

we now have to take \({{\text{A}}_n}{{\text{A}}_1}\)

thus the cycle is \({{\text{A}}_1}{{\text{A}}_2}{{\text{A}}_3} \ldots {{\text{A}}_{n - 1}}{{\text{A}}_n}{{\text{A}}_1}\)     A1A1

Note: Final A1 is for \({{\text{A}}_n}{{\text{A}}_1}\).

(ii)     smallest edge from \({{\text{A}}_1}\) is \({{\text{A}}_1}{{\text{A}}_2}\) of weight 3, smallest edge from \({{\text{A}}_2}\) (to a new vertex) is \({{\text{A}}_2}{{\text{A}}_3}\) of weight 5, smallest edge from \({{\text{A}}_{n - 1}}\) (to a new vertex) is \({{\text{A}}_{n - 1}}{{\text{A}}_n}\) of weight \(2n - 1\)     (M1)

weight of \({{\text{A}}_n}{{\text{A}}_1}\) is \(n + 1\)

weight is \(3 + 5 + 7 +  \ldots  + (2n - 1) + (n + 1)\)     A1

\( = \frac{{(n - 1)}}{2}(2n + 2) + (n + 1)\)    M1A1

\( = n(n + 1)\) (which is an upper bound)     A1

Note: Follow through is not applicable.

[7 marks]

put a marker on each edge \({{\text{A}}_i}{{\text{A}}_j}\) so that \(i\) of the weight belongs to vertex \({{\text{A}}_i}\) and \(j\) of the weight belongs to vertex \({{\text{A}}_j}\)     M1

the Hamiltonian cycle visits each vertex once and only once and for vertex \({{\text{A}}_i}\) there will be weight \(i\) (belonging to vertex \({{\text{A}}_i}\)) both going in and coming out     R1

so the total weight will be \(\sum\limits_{i = 1}^n {2i = 2\frac{n}{2}(n + 1) = n(n + 1)} \)     A1AG

Note: Accept other methods for example induction.

[3 marks]